算法编程练习 数组中出现次数超过一半的数字

Reply Share

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

题目分析：

如果是排好序的数组，那么只需一遍遍历即可找出是否存在一个数字出现次数超过数组长度的一半。因此如果先对数组进行快速排序，再一次遍历可以得到结果，此时时间复杂度为O(nlogn)。
此时的时间复杂度相对较高，考虑换一种思路解决该问题。数组中有一个数字出现的次数超过了数组长度的一半，如果将这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字，也就是统计学中的中位数。
我们可以考虑先随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的全部在它的左边，比选中的数字大的全部在右边。如果这个选中的数字的下标刚好是n/2，那么这个数就是数组的中位数。如果这个选中的数字的下标大于n/2，那么中位数应该在它的左侧，应该在它的左侧查找。如果这个选中的数字的下标小于n/2，那么中位数应该在它的右侧，应该在它的右侧查找。可以用下述代码实现：

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
int MoreThanHalfNum(vector<int> numbers){
    if(numbers.empty())    //向量容器为空
        return 0;
    int length=numbers.size();  //输入数据非法
    if(CheckInvalidArray(numbers,length))
        return 0;

    int middle=length>>1;    //位移运算代替除2
    int start=0;
    int end=length-1;
    int Partition(numbers,length,start,end);  

    while(index!=middle){
        if(index>middle){
            end=index-1;
            index=Partition(numbers,length,start,end);
        }
        else{
            start=index+1;
            index=Partition(numbers,length,start,end);
        }
    }
    int result=numbers[middle];
    if(!CheckMoreThanHalf(numbers,length,result))
        result 0;
    return result;
}

bool g_bInputInvalid=false;
    
bool CheckInvalidArray(vector<int> numbers,int length){
    g_bInputInvalid=false;
    if(numbers.empty() || length<=0)
        g_bInputInvalid=true;
        
    return g_bInputInvalid;
}
    
bool CheckMoreThanHalf(vector<int> numbers,int length,int number){
    int times=0;
    for(int i=0;i< length;++i){
        if(numbers[i]==number)
            times++;
        }
        
    bool isMoreThanHalf=true;
    if(times*2<=length){
        g_bInputInvalid=true;
        isMoreThanHalf=false;
    }
    return isMoreThanHalf;
}  

int Partition(vector<int> data,int length,int start,int end){
    if(data.empty())
        return NULL;
    if(data.size()!=length || length<=0 || start<0 || end>=length)
        throw new std::exception("Invalid Parameters");

    int index=RandomInRange(start,end);
    Swap(&data[index],&data[end]);

    int small=start-1;
    for(index=start;index<end;++index){
        if(data[index]<data[end]){
            ++small;
            if(small!=index)
                Swap(&data[index],&data[small]);
        }
    }
    ++small;
    Swap(&data[small],&data[end]);
}

除了上述思路之外，数组中一个数组出现的次数超过数组的长度的一半，那么它出现的次数比其他数字出现次数的累加和还要多。我们如果在遍历时储存两个值，一个是数组中的值，一个为出现的次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，我们将次数加1，如果出现的数字不同，则将次数减1，次数为零的时候需要保存下一个数字，次数设为1.如果最终我们储存的数字出现的次数超过数组长度的一半，那么肯定是最后一次把次数设为1的数字。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int MoreThanHalfNum_Solution(vector<int> numbers) {
         int length=numbers.size();
         if(CheckInvalidArray(numbers,length))
            return 0;
        
        int result=numbers[0];
        int times=1;
        for(int i=1;i<length;++i){
            if(times==0){
                result=numbers[i];
                times=1;
            }
            else if(numbers[i]==result)
                times++;
            else
                times--;                
        }
        if(!CheckMoreThanHalf(numbers,length,result))
            result=0;
            
        return result;        
        
    }

1