寻找多数元素问题
问题:假如现在有一个序列,已知其中一个数的此书超过50%,请找出这个数。比如3、3、1、1、3、2、3中,出现次数超过50%的数是3 。
方法1:两两比较,分别记录数字的出现次数,2个for循环就可以解决。时间复杂度O(N^2)。
方法2:排序后,如果这个数出现的次数大于50%的话,排序之后就应该就是位于n/2位置的那个数。
方法3:“寻找多元素问题”,我们很容易的看出来,在一个序列中如果去掉2个不同的元素,那么原序列中的出现次数超过50%的数,在新的序列中还是超过50%,因此我们只要按照序列依次扫描,先把A[0]赋值给c,增加个计数器,count = 1;然后向右扫描,如果跟c相同,则count++,不同,那么count --,这个真是我们从上面那个结论里得出的,一旦count == 0了,把c赋值为A[i+1],count = 1;,重复该过程,直到结束,这个时候,c就是那个超过50%的数。遍历一遍,时间复杂度为O(N)。
package candidate;
public class Candidate
{
// 递归实现
public int candidateSort(int[]a, int start, int end)
{
int c = a[start];
int count = 1;
int j;
for (j=start;j<end && count>0;j++)
{
if (c == a[j])
{
count++;
}
else {
count--;
}
}
if (j == end)
{
return c;
}
else {
return candidateSort(a, j+1, end);
}
}
// 循环实现
public int candidateSort(int[] a)
{
int c = a[0];
int count = 0;
for (int i=1; i<a.length;i++)
{
if (c == a[i])
{
count++;
}
else if (count < 0) {
c = a[i];
count = 0;
}
else {
count--;
}
}
return c;
}
转载于:https://blog.51cto.com/coollast/1887930