学校联网网站建设,新网站上线 怎么做seo,建一个做笔记的网站,西安黑马程序员培训机构定义#xff1a;序列中的多数元素是指在一个元素个数为n的序列中#xff0c;多数元素出现次数大于[n/2].寻找元素方法很多#xff1a;1.可以暴力搜索#xff0c;将每个元素都与其他元素作比较#xff0c;然后统计该元素出现的次数#xff0c;时间复杂度为O(n2)#xff1…定义序列中的多数元素是指在一个元素个数为n的序列中多数元素出现次数大于[n/2].寻找元素方法很多1.可以暴力搜索将每个元素都与其他元素作比较然后统计该元素出现的次数时间复杂度为O(n2)2.可以先排序然后再统计每个元素出现的次数时间复杂度为O(nlogn)3.可以寻找中间值元素因为多数元素在序列中必为中间值元素时间复杂度是O(n)(寻找中间值元素可以运用寻找第k小元素算法http://www.cnblogs.com/7hat/p/3411756.html)这里要介绍第4种方法时间复杂度也是O(n)但是隐藏常数会比寻找中间值的方法要小。算法基于以下观察在原序列中去除两个不同的元素后那么在原序列中的多数元素在新序列中还是多数元素。算法基本思路(1)在寻找多数元素的过程中将计数器置1遇到相同元素则计数器加1遇到不同元素则计数器减1一直到计数器等于0或遍历完整个序列。由此可见计数器的值表示当前元素抵消掉不同元素后的出现次数(2)当计数器在遍历完整个序列前就已经是0则忽略掉已经遍历过的元素(可以看作两两抵消不影响序列中的多数元素)跳到下一个元素然后计数器重新置1重复上述步骤一直到遍历完整个元素(3)当遍历完整个序列后算法会返回一个值此时我们还需要检测一次这个值是否真的是多数元素即遍历统计一次。这一步不可或缺。因为上述两个步骤到了遍历完序列后必将返回一个值无论序列有无多数元素。此值存在三种情况第一它真的是多数元素第二它只是序列后面的某个元素刚好抵消完序列第三两者皆是。我们必须检测一次。算法的实现基本上和上面思路一样这里我给出递归代码和迭代代码。需要注意的是因为有可能不存在多数元素所以需要一个boolean变量来表示是否找到。public classmajority{private static booleanflag;private static int candidate(int k, int[] A){//find the candidate may be a majorityint i k;int x A[k];int count 1; //indicates the current element occurrences, after offset different elementswhile(i A.length-1 count 0){//remove two different elements, the majority element will not changei ;if(A[i] x){count;}else{count--;}}//there are three cases of x: x is the majority element or x is the last element or bothif(i A.length-1)returnx;return candidate(i1, A);}public static int findMajority(int[] A){//find the majorityint x candidate(0, A);int count 0;for(int i 0; i A.length; i ){//Test whether x is really the majority of elements in the arrayif(A[i] x){count;}}if(count A.length/2){flag true;returnx;}else{flag false;return 0;}}public static int findMajority1(int[] A){//Iterationint x 0;for(int i 0; i A.length; i ){int count 1;xA[i];while(i A.length-1 count 0){i;if(A[i] x){count;}else{count--;}}}int count 0;for(int i 0; i A.length; i ){if(A[i] x)count ;}if(count A.length/2){flag true;returnx;}else{flag false;return 0;}}public static voidmain(String[] args){int[] A {2, 3, 2, 4, 2};int x1 findMajority(A);if(flag){System.out.println(Found it: x1);}else{System.out.println(Not found!);}int x2 findMajority1(A);if(flag){System.out.println(Found it: x2);}else{System.out.println(Not found!);}}}Java
