上课老师留的算法题,进来看看

Question

Quiz:有数组T[0 - n-1],对任一元素x,设S(x) = {i | T[i] = x}.当|S(x)| > n /2时,称x为T的主元素.请设计一个线型时间算法实现此算法.
note: O(n)
如果有时间就发发代码看看,没空交流下思想.

Answer 1

看问题也是一种能力的说,楼上的不对.
"|S(x)|"的意思是S(x)的模,也就是个数.

Answer 2

|S(x)| > n /2时,称x为T的主元素.
没看出这句话对题目有什么作用，感觉废话一句。
它只是提出了一个概念，没说这个概念有啥用。我还可以在题目中加上“两条永不相交的直线，称为平行线”，然后就不告诉你“平行线”和题目有啥关系～～～～～～

Answer 3

max = 0
for i=0 to n-1 {
  temp = ++buffer[t[i]]
                  ^^^^重点、精华
  if (temp>max) max=temp
}
if max>n/2 则OK

Answer 4

System.out.println("results following:");
for(int i=0;i<n;i++)++score[T[i]];
for(int i=0;i<n;i++)
if(score[i]>n/2){
   System.out.println("{i|T[i]="+i+"}");
}
System.out.println("That's all");

Answer 5

我一位只要最多的，没什么用。
看看puerbegger的，一样的思路。

Answer 6

楼上思路先不说对不对,我问你排序的时间复杂度是多少?能到O(n)吗,显然不对...快速排序的时间复杂度是O(nlogn),楼上几位的代码我看了显然题目没有看懂.

Answer 7

/**判断输入的数列是否有主元素
      */ 
     private static boolean hasMaster(int data[], int n) 
     { 
        int count=0;    //保存计数 
        int seed;       //保存参照元素 
         
        seed = data[0]; 
         
        for(int i=1; i<n; i++) 
        { 
            if(seed == data[i])     //如果数据相同，计数加一 
            { 
                count++; 
            } 
            if(seed == data[i]) 
            { 
                if(count>0) 
      
           { 
                    count--;        //如果数据不同，则计数减一 
                                    //相当于删除两个不同的元素 
                                    //不会对主元素造成影响 
                } 
                else 
                { 
                    seed = data[i]; //计数为零时，seed不可能为主元素 
                                    //读入新数据 
                } 
            } //end of if 
        } //end of for 
         
        //因为最终得到的seed元素有可能是序列最末位的两个元素之一 
        //因此，这里还需要验证 
        count = 0; 
        for(int i=0; i<n; i++) 
        { 
            if (seed == data[i]) 
                count++; 
        } 
         
        if(count>(n/2)) 
        { 
            return true; 
        } 
         
        return false;    
         
     } 
}

Answer 8

设T[0:n-1]是n个元素的数组。对任意一个元素x，设S(x)={i|T[i]=x}。当|S(x)|〉n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0:n-1]是否有一个主元素。
b) 分析
通过对问题目的性的研究，可以得到这样的一个结论：
在元素数组中，删去不同的两个元素，数组的主元素保持不变。
按照这样的思路，我们可以不断缩小问题的规模，最终使问题得解：
设置变量Seed用于存储当前候选元素，初始化为数组首元素a[0]；
设置变量count用于控制候选元素，初始化为1；
从第二个元素a[1]开始遍历数组，并与Seed相比较：
相同，则count加1，读入下一个元素；
不同，则count减1，读入下一个元素：相当于删去两个不同元素，缩小问题规模；
如果count小于0则Seed不是主元素候选，读入下一个元素，count加1。
这样一次遍历之后，得到的Seed就是主元素的候选；
但因为最终得到的Seed元素有可能是序列最末位的两个元素之一，所以还需要验证。
我们再次遍历数组，得到Seed出现的次数，与总数的一半比较来验证。

Answer 9

-->
http://acm.zju.edu.cn/show_problem.php?pid=2132
-->
/*
 ** found 2005-11-2
 ** by kingly
 ** 
 */#define test
#ifdef test
#include<iostream.h>
#include<fstream.h>
#endif#include<stdio.h>int main()
{
    #ifdef test
     freopen("in.txt", "r" ,stdin);
     freopen("out.txt","w",stdout);
     //ofstream cout("out.txt");
    #endif
   int counter,answer,n,data;
   int bb = 0;  
   while(1)
   {
           scanf("%d",&n);
           if(n<0)break;
           counter=0;
           for(int i=0;i<n;i++)
      {
         scanf("%d",&data);
         if(!counter){
                answer = data;               
                counter=1;
                continue;
         }        
         if(answer==data){
             ++counter;             
         }else{
               --counter;               
         }
      }     
      printf("%d\n",answer);
   }
}

Answer 10

楼上思路先不说对不对,我问你排序的时间复杂度是多少?能到O(n)吗,显然不对...快速排序的时间复杂度是O(nlogn),楼上几位的代码我看了显然题目没有看懂.－－－－－－－－－－－－－－－－－－－－－－－－－－－－
恩。
既然这样，那也不一定要排序的啊。
直接找到数列中第n大的数字，时间复杂度为O（n）。

Answer 11

楼主啊，把题目说清楚也是一种能力，
请设计一个线型时间算法实现此算法.
这个此算法是什么？
还是看了liuguangliang才明白的
liuguangliang思路不错，应该是正解吧