微软面试100题(74):数组中出现次数超过长度的一半/一半减一的元素

数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

昨天看到了扩展问题，如果有且只有一个的出现最多的那个数字出现的次数是数组长度的一半呢？又或者是一半减1？
这个题目网上流传的解法是每遇到2个不同的数，就删除，剩下的就是那个出现次数超过一半的数字。这个方法对于超过一半的情况可以成立，对于扩展问题就不再行得通了。
坐公交想了比较久，最后有如下的结果和证明。
做完后又考虑了网上流传的做法，想想也是一样的，对于一个长度为2n的数组，如果有个数出现次数超过n,那么至少有1组，连续2个数是重复的。
相应的，如果出现的次数为n, 那么至少有一组连续3个数是重复。每3个不重复的数删除一次
如果是n-1,就是一组至少有连续4个数重复。每4个不重复的数删除一次
本质上一样的。相比较之下，我的证明过程就过于复杂了，不是那么直观。


方法：
用两个数组rnum,roccur,大小都为2，记录最近2个读到数字的值和其出现的次数.
每读到一个数，查询其在rnum是否存在：
    如果存在，将对应出现的次数加1
    如果不存在，替换出现次数比较少的那个元素，并将其次数置为1
当读取结束时，最后的记录里，出现次数比较多的那个元素，就是所求的数字
例如对于数组{10,10,20}来说，遍历完成时。
rnum[0] = 10 roccur[0] = 2
rnum[1] = 20 roccur[1] = 0


对于出现次数超过一半，需要保存最近读到的两个数字和出现的次数，
如果是出现的次数最小是长度的一半，就需要保存3个数的记录，
相应的，出现最多的那个数最少出现次数是数组一半减1就需要保存4个数的记录。
还可以继续扩展。


这里只证明了出现次数超过一半的情况，如果出现次数至少为一半，或者一半减一，也可以通过相同的逻辑证明。
数学归纳证明算法如下.

假设有2k+1个数字，出现次数超过一半的数字为i,那么i出现的次数i.count，有k+1<=i.count<=2k+1

当k=1时，有3个数字，遍历完成后
显然i.count = 2,设另一个数字为j,j.count =1
i.count>j.count,所以最终结果为i,算法成立。

假设当k=n时，算法成立
i.count = g
j.count = h
有 n+1<= g <=2n+1
    0<= h <=n
且i.count>j.count
最后结果为i.

当k = n+1时：
数字总数比k=n是增加了两个.
增加后依然i出现的次数超过一半
                2n+3>i.count>= n+2
考虑这增加的数字：
    a.若增加的数字都为i,那么显然依然有
        i.count = g + 2;
        j.count = h;
         i.count>j.count;
        算法成立

    b.若增加的数中一个为i,
                i.count = g+1;
          若另一个为j则 j.count = h+1;
          若另一个不为j则会替换j,此时 j.count = 1；
          依然有 i.count>g.count, 算法成立

        c.若增加的数都为j.
                i.count = g
                j.count = h+2;
          当h取最大值n时，
          h+2=n+2;  g = n+1;
          但是j出现的次数n+2 超过了总数量的一半(n+1)，和题设i出现的次数超过一半矛盾。
          该假设不成立。
       c.若增加的数既不是i,也不是j.那么j会被最新的数替代
                i.count = g
                j.count = 1
          算法依然成立。
          

                                      

#include <stdlib.h>
#include <stdio.h>

int getNumOverHalf(int *nums, int size){
    int record[2][2] = {{0}};
    int i = 0;
    for(;i<size;i++){
        if(record[0][0] == nums[i]){
            record[0][1]++;
            continue;
        }
        if(record[1][0] == nums[i]){
            record[1][1]++;
            continue;
        }

        if(record[0][1]<=record[1][1]){
            record[0][0] = nums[i];
            record[0][1] = 1;
        }
        else{
            record[1][0] = nums[i];
            record[1][1] =1;
        }
    }
    return record[0][1]>record[1][1]? record[0][0]:record[1][0]
}

int main(){
    int input[] = {1,2,5,1,5,1,1};
    int tar = getNumOverHalf(input, sizeof(input)/sizeof(int));
    printf("%d \n", tar);
}