算法问题

Question

大小为N到数组A，其主要元素是一个出现次数超过N/2的元素。试编写运行时间为O(N)到程序，求给定Nge元素的数组的主要元素。如果没有主要元素，程序应该指出！
我们学校软件技能大赛的算法题目。。
大家讨论下！！
用C#写下！

Answer 1

public int GetMember(int[] arr)
{
   int count=0;
   for(int i=0;i<arr.Length;i++)
   {
       count=0;
       for(int j=0;j<arr.Length;j++)
       {
           if(arr[j]==arr[i])
           {
               count++;
           }
       }
       if(count>=arr.Length/2)
       {
            return arr[i];   
       }   }
   return -1;
}

Answer 2

    /// <returns>
    /// return 0 if not found
    /// otherwise the count of the number which counts for more than half of the array.
    /// </returns>
    static int GetPincipalElement(int[] A, ref int element)
    {
        Dictionary<int, int> dict = new Dictionary<int, int>();
        int maxCount = 0;        foreach (int el in A)
        {
            if (dict.ContainsKey(el))
            {
                if (++dict[el] > maxCount)
                {
                    maxCount = dict[el];
                    element = el;
                }
            }
            else
            {
                dict[el] = 1;
            }
        }        return maxCount > A.Length / 2 ? maxCount : 0;
    }

Answer 3

public object GetMember(object[] arr) 
{ 
  int count=0; 
  Hashtable hash = new Hashtable();
  for(int i=0;i <arr.Length;i++) 
  { 
      if(hash.Contains(arr[i]))
           hash[arr[i].ToString()] = (int)hash[arr[i].ToString()] + 1;
      else
           hash.Add(hash[arr[i].ToString()],1);
           } 
      if(count>=arr.Length/2) 
      { 
            return arr[i];  
      } 
  } 
  foreach(object obj in hash.Keys)
  {
      if((int)hash[obj.ToString()] > arr.Length/2)
           return obj
  }
  return null; 
}
直接在网页上写的代码,没有VS的提示都不知道对不对.请各位牛牛指正

Answer 4

改正错误:
public object GetMember(object[] arr) 
{ 
  int count=0; 
  Hashtable hash = new Hashtable(); 
  for(int i=0;i <arr.Length;i++) 
  { 
      if(hash.Contains(arr[i])) 
      {
          if((int)hash[obj.ToString()] + 1 > arr.Length/2) 
return obj;
          hash[arr[i].ToString()] = (int)hash[arr[i].ToString()] + 1; 
          
      }
      else 
          hash.Add(hash[arr[i].ToString()],1); 
         
     
  }   
  return null; 
} 

Answer 5

4楼的Dictionary是2.0里面的,还没用过,惭愧惭愧

Answer 6

赞成，借助Hashtable基本是可以保证O(N)的时间要求。

Answer 7

        private int GetN2(int[] a)
        {
            int n = a.Length;
            Hashtable ht=new Hashtable ();
            for (int i = 0; i < n; i++)
            {
                if (!ht.ContainsKey(a[i]))
                {
                    ht.Add(a[i], 1);
                }
                else
                {
                    int p = (int)(ht[a[i]]);
                    p++;
                    if(p>(n/2)) { return a[i];}
                    ht[a[i]] = p;
                }
            }
            return -1;        }

Answer 8

大家看看我的办法怎么样？:)
  private int GetMember(int[] A)
            {            //最多元素的个数
            int maxCount = 0;            //和数组A一样的ArrayList
            ArrayList al = new ArrayList();
            for(int i=0;i<A.Length;i++)
            {
                al.Add(A[i]);
            }
           
            //为了得到“主元素”，比较相邻两个元素值，如果不相同，则把这两个元素都删除
            //如果相同，则和后续元素相比，最后剩的元素应该就是“主元素”
           for(int dist=1;dist<=al.Count-1;)
           {
               if(!al[0].Equals(al[dist]))
               {
                   al.Remove(al[0]);
                   al.Remove(al[dist-1]);
               }
               else
               {
                   dist++;
               }
           
           }            //找到主元素后，找查一遍，计算个数
            for(int i=0;i<A.Length;i++)
            {
                if (A[i].Equals(al[0]))
                    maxCount++;
            }
        
            if(maxCount>A.Length/2)
            {
                MessageBox.Show("存在这样的主元素，为"+al[0].ToString());
            }
            else
            {
                MessageBox.Show("不存在这样的元素"); 
            
            }            }

Answer 9

public object GetMember(object[] arr) 
{ 
  int count=0; 
  Hashtable hash = new Hashtable(); 
  for(int i=0;i <arr.Length;i++) 
  { 
      if(hash.Contains(arr[i])) 
          hash[arr[i].ToString()] = (int)hash[arr[i].ToString()] + 1; 
      else 
          hash.Add(hash[arr[i].ToString()],1); 
          } 
      if(count>=arr.Length/2) 
      { 
            return arr[i];  
    …