By

Contents
  1. 1. 寻找数组中出现次数超过一半的数字
  2. 2. 扩展1：如果改为该数字长度恰好为数组长度的一半，又该如何求？
  3. 3. 扩展2：寻找数组中所有出现次数超过1/3的数字
  4. 4. 扩展3：寻找出现次数超过1/4的数字

寻找数组中出现次数超过一半的数字

  • 方法1 对数组排序，然后顺次查找其中最多的；
  • 方法2 对数组排序，最中间一个肯定为要找的数字,时间复杂度O(NlogN)；
  • 方法3 顺次消去数组中两个不同的数，最后剩下的肯定为要找的数字，时间复杂度O(N).

更进一步，考虑到这个问题本身的特殊性，我们可以在遍历数组的时候保存两个值：一个candidate，用来保存数组中遍历到的某个数字；一个nTimes，表示当前数字的出现次数，其中，nTimes初始化为1。当我们遍历到数组中下一个数字的时候：
如果下一个数字与之前candidate保存的数字相同，则nTimes加1；
如果下一个数字与之前candidate保存的数字不同，则nTimes减1；
每当出现次数nTimes变为0后，用candidate保存下一个数字，并把nTimes重新设为1。 直到遍历完数组中的所有数字为止。
举个例子，假定数组为{0, 1, 2, 1, 1}，按照上述思路执行的步骤如下：
1.开始时，candidate保存数字0，nTimes初始化为1；
2.然后遍历到数字1，与数字0不同，则nTimes减1变为0；
3.因为nTimes变为了0，故candidate保存下一个遍历到的数字2，且nTimes被重新设为1；
4.继续遍历到第4个数字1，与之前candidate保存的数字2不同，故nTimes减1变为0；
5.因nTimes再次被变为了0，故我们让candidate保存下一个遍历到的数字1，且nTimes被重新设为1。最后返回的就是最后一次把nTimes设为1的数字1。
思路清楚了，完整的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public  int majorityElement(int[] nums) {
   int c = 0;
   int times = 0;
   for(int i=0;i<nums.length;i++){
	   if(times==0){
		   c=nums[i];
		   times=1;
	   }else{
    	   if(nums[i]==c){
    		   times++;
    	   }else{
    		   times --;
    	   }
	   }
   }
   return c;
}

扩展1：如果改为该数字长度恰好为数组长度的一半，又该如何求？

分析：先消掉3个不同的数字，再使用问题1的方法求解。因为消除3个不同数字时，Major Element最多消除一个，则，这样之后水王 Major Element个数就大于总数的一半了，就变成原问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
int Find(int* ID, int N);
int main(void)
{
    int ID[6] = {2,1,2,1,3,1};
    printf("水王id: %d\n",Find(ID,6));
    return 0;
}
int Find(int* ID, int N)
{
    int candidate;
    int nTimes = 0, i;
    int flag = 0;
    int del[3];
    del[0] = ID[0];
    for(i = 1; i < N; i++)
    {
        if((ID[i] != del[0]) && (flag == 0))
        {
            del[1] = ID[i];
            flag = 1;
            continue;
        }
        if((ID[i] != del[0]) && (ID[i] != del[1]) && (flag == 1))
        {
            flag = 2;
            continue;
        }
        if(nTimes == 0)
        {
             candidate = ID[i], nTimes = 1;
        }
        else
        {
            if(candidate == ID[i])
                nTimes++;
            else
                nTimes--;
        }
    }
    return candidate;
}

扩展2：寻找数组中所有出现次数超过1/3的数字

分析 ： 这样的数字最多有2个，但是可能会只有一个，可以用两个candidate和两个times。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
	//需要考虑的情况：
//	1、nums长度为1
//	2、major element只有一个，就是有一个超过1/2，另一个没有
    public static List<Integer> majorityElement(int[] nums) {
    	List<Integer> res = new ArrayList<Integer>();
    	if(nums==null || nums.length==0) return res;
        int candidate1 = 0;
        int candidate2 = 0;
        int time1=0;
        int time2=0;
        for(int n:nums){
        	if(n==candidate1){
        		time1++;
        	}else if(n==candidate2){
        		time2++;
        	}else if(time1==0){
        		candidate1 = n;
        		time1 = 1;
        	}else if(time2==0){
        		candidate2=n;
        		time2=1;
        	}else{
        		time1--;
        		time2--;
        	}
        }
        time1=0;
        time2=0;
        for(int n:nums){
        	if(n==candidate1) time1++;
        	else if(n==candidate2) time2++;
        }
        if(time1>(nums.length/3)){
        	res.add(candidate1);
        }
        if(time2>(nums.length/3)){
        	res.add(candidate2);
        }
        return res;
       
    }

扩展3：寻找出现次数超过1/4的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
void Find(int* ID, int N);
int main(void)
{
    int ID[] = {5,6,7,1,2,1,2,1,2,3,3,4,3,2,1,3,2,1,2,1,3};
    Find(ID,21);
    return 0;
}
void Find(int* ID, int N)
{
    int nTimes[3], i;
    int candidate[3];
    nTimes[0]=nTimes[1]=nTimes[2]=0;
    candidate[0]=candidate[1]=candidate[2]=-1;
    for(i = 0; i < N; i++)
    {
        if(ID[i]==candidate[0])//这几个并列的思想很重要，好好想想
        {
             nTimes[0]++;
        }
        else if(ID[i]==candidate[1])
        {
             nTimes[1]++;
        }
        else if(ID[i]==candidate[2])
        {
             nTimes[2]++;
        }
        else if(nTimes[0]==0)
        {
             nTimes[0]=1;
             candidate[0]=ID[i];
        }
        else if(nTimes[1]==0)
        {
             nTimes[1]=1;
             candidate[1]=ID[i];
        }
        else if(nTimes[2]==0)
        {
             nTimes[2]=1;
             candidate[2]=ID[i];
        }
        else//新的id和已选的三个id不同的时候，让已选的三个id同时-1
        {
             nTimes[0]--;
             nTimes[1]--;
             nTimes[2]--;
         }
    }
    //这里默认考虑超过1/4的元素有3个，实际上可能还有2,1个
    printf("id:   %d %d %d\n",candidate[0],candidate[1],candidate[2]);
    printf("times:%d %d %d\n",nTimes[0],nTimes[1],nTimes[2]);
    return;
}
Contents
  1. 1. 寻找数组中出现次数超过一半的数字
  2. 2. 扩展1：如果改为该数字长度恰好为数组长度的一半，又该如何求？
  3. 3. 扩展2：寻找数组中所有出现次数超过1/3的数字
  4. 4. 扩展3：寻找出现次数超过1/4的数字