请教各位大哥一个算法问题

Question

如果排序后可以得到，但是是O（nlogn）的
关注

Answer 1

设循环，将所有数每出现一次统计一次，若count(i)>o.5总数，则正如你所求。

Answer 2

a[10]={2, 2 ,2 ,2 ,3 ,5, 2, 3, 4, 2   }
设temp[a.length]
先把各个不相同的数放到temp里面
然后循环比较，统计每个数出现的次数

Answer 3

循环一次，设标记flag（是否有主元素）初值false，记录每个元素出现的次数（count[i]++），记录的时候判断，如果当前元素出现次数已经>0.5*a.length()则循环结束，有主元素，将flag置true。否则如果循环完毕flag仍为false，无主元素。需要程序代码吗？自己应该可以写出来吧，不难。

Answer 4

当然是O(n)了，只是将n元数组循环一次啊        String a[]={"2", "2" ,"2" ,"2" ,"3" ,"5", "2", "3", "4", "2"};
        Vector indexV = new Vector();
        Vector element = new Vector();
        for(int i=0;i<a.length;i++){
            if(!indexV.contains(a[i])){
                indexV.add(a[i]);
                element.add("0");
            }else{
                int j = indexV.indexOf(a[i]);
                int t = Integer.parseInt((String)element.get(j))+1;
                element.set(j,String.valueOf(t));
                if(t>=0.5*a.length){
                    flag=true;
                    System.out.println("element :"+a[i]+" is the main element");
                }
            }

Answer 5

为了方便，我把数组变成了String型的

Answer 6

Vector是复杂变量，indexV.contains(a[i])、indexV.add(a[i]);可能都会去遍历，那就不是一次的问题。而是n2

Answer 7

        String a[]={"2", "2" ,"2" ,"2" ,"3" ,"5", "2", "3", "4", "2"};
        Vector indexV = new Vector();
        Vector element = new Vector();
        for(int i=0;i<a.length;i++){
            if(!indexV.contains(a[i]))
          {
                indexV.add(a[i]);
                element.add("0");
          }else
              {
                int j = indexV.indexOf(a[i]);
                int t = Integer.parseInt((String)element.get(j))+1;
                element.set(j,String.valueOf(t));
                if(t>=0.5*a.length){
                    flag=true;
                    System.out.println("element :"+a[i]+" is the main element");
                                    }
              }

Answer 8

为什么排序后得到是O(nlogn)的 
可以先用O(n)排完序  再做其他操作  使之还是O(n)吗

Answer 9

基数排序是0（rn＋d），看似0（n），但是似乎不适合你的这种数值排序。

Answer 10

exitzhang(exit) 你提供的也不能算是O（n）吧，(!indexV.contains(a[i])本身就是个O（n）的，再放如FOR循环肯定是O（n2）了。
我整理出的思路是先确定出现次数，然后寻找出现次数的最大值，用2次FOR循环，
关键在于确定出现次数时很难限制为O（n）。

Answer 11

zjb030320134(环岛路)你的具体问题是什么啊，看起来你把你的具体问题抽象为现在的问题
恐怕是很难解决的，不如把具体问题贴出来看大家有什么好办法。

Answer 12

zjb030320134(环岛路) ( ) 信誉：100  2003-12-20 20:46:00  得分:0 
为什么排序后得到是O(nlogn)的 
可以先用O(n)排完序  再做其他操作  使之还是O(n)吗如果你能用O(n)排序，我可以提供O(n)的查找主元算法，既然已经排序过了，
可以再用一个FOR循环查找每个元素出现的次数，
for (int i=1;i<arg.length;i++)
{
  if a[i]=a[i-1] then  设定一下计数器并比较是否>=arg.length/2
}
这样加上你的排序是2 O(n)，其实也就是O(n)