面试题29：数组中出现次数超过一半的数字

根据数组特点找出O(n)的解法：

考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1。如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

原理就是如果确实存在出现次数超过一半的数字，那么他出现的次数一定可以抵消掉没有其他数字出现的次数。当然如果输入的例子不对也可能通过，所以最后需要检查

 1 bool g_bInputInvalid = false;
 2 
 3 bool CheckInvalidArray(int* numbers, int length)
 4 {
 5     g_bInputInvalid = false;
 6     if(numbers == NULL && length <= 0)
 7         g_bInputInvalid = true;
 8 
 9     return g_bInputInvalid;
10 }
11 
12 bool CheckMoreThanHalf(int* numbers, int length, int number)
13 {
14     int times = 0;
15     for(int i = 0; i < length; ++i)
16     {
17         if(numbers[i] == number)
18             times++;
19     }
20 
21     bool isMoreThanHalf = true;
22     if(times * 2 <= length)
23     {
24         g_bInputInvalid = true;
25         isMoreThanHalf = false;
26     }
27 
28     return isMoreThanHalf;
29 }
30 
31 int MoreThanHalfNum_Solution2(int* numbers, int length)
32 {
33     if(CheckInvalidArray(numbers, length))
34         return 0;
35  
36     int result = numbers[0];
37     int times = 1;
38     for(int i = 1; i < length; ++i)
39     {
40         if(times == 0)
41         {
42             result = numbers[i];
43             times = 1;
44         }
45         else if(numbers[i] == result)
46             times++;
47         else
48             times--;
49     }
50  
51     if(!CheckMoreThanHalf(numbers, length, result))
52         result = 0;
53  
54     return result;
55 }

基于Partition的方法：

Partition函数既是快速排序的基础，也可以用来查找n个数中第K大的数字

 1 int MoreThanHalfNum_Solution1(int* numbers, int length)
 2 {
 3     if(CheckInvalidArray(numbers, length))
 4         return 0;
 5  
 6     int middle = length >> 1;
 7     int start = 0;
 8     int end = length - 1;
 9     int index = Partition(numbers, length, start, end);
10     while(index != middle)
11     {
12         if(index > middle)
13         {
14             end = index - 1;
15             index = Partition(numbers, length, start, end);
16         }
17         else
18         {
19             start = index + 1;
20             index = Partition(numbers, length, start, end);
21         }
22     }
23  
24     int result = numbers[middle];
25     if(!CheckMoreThanHalf(numbers, length, result))
26         result = 0;
27 
28     return result;
29 }

partition:

int partition(vector<int> &num, int low, int high)
    {
        int pivot = num[low];
        while(low < high)
        {
            while(low < high && num[high] >= pivot)
                high--;
            num[low] = num[high];
            while(low < high && num[low] <= pivot)
                low++;
            num[high] = num[low];
        }
        num[low] = pivot;
        return low;
    }

还可以利用map

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        map<int,int> num_count;
        vector<int>::iterator ite = numbers.begin();
        while(ite != numbers.end())
            num_count[*ite++]++;
        int len = numbers.size();
        int helf = len >> 1;
        map<int,int>::iterator ite1 = num_count.begin();
        while(ite1 != num_count.end())
        {
            if((*ite1).second > helf)
                return (*ite1).first;
            ite1++;
        }
        return 0;
    }
};