题目描述 牛客网

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

题目解读

• 剑指Offer 205
• 思路一、基于 Partition 函数的时间复杂度为 O(n) 的算法
• 思路二、基于数组特点找出时间复杂度为 O(n) 的算法
• 思路三、map 实现。key存储数字，value存储次数，出现次数超过数组长度的一半则找到数字

代码

• 思路一、基于 Partition 函数的时间复杂度为 O(n) 的算法
  考虑数组的特性：数组中有一个数字出现的次数超过数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数组。
  这种算法受到快速排序的启发

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int Paritition1(vector<int>& numbers, int left, int right){
        int pivot = numbers[left];
        while(left < right){

            while(left < right && numbers[right] >= pivot){
                right --;
            }
            numbers[left] = numbers[right];

            while(left < right && numbers[left] <= pivot){
                left ++;
            }
            numbers[right] = numbers[left];
        }
        numbers[left] = pivot;
        return left;
    }

    bool checkVality(vector<int> numbers, int result){
        bool vality = true;
        int times = 0;
        int len = numbers.size();
        for(int i=0; i < len; i++){
            if(result == numbers[i]){
                times ++;
            }
        }

        if(times * 2 <= len){
            vality = false;
        }
        return vality;
    }

    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        if(numbers.size() == 0){
            return 0;
        }

        int middle = numbers.size() >> 1;
        int left = 0;
        int right = numbers.size() - 1;
        int pivot = Paritition1(numbers, left, right);

        while(pivot != middle){
            if(pivot > middle){
                right = pivot - 1;
            }
            else{
                left = pivot + 1;
            }
            pivot = Paritition1(numbers, left, right);
        }

        int result = numbers[middle];
        if(!checkVality(numbers, result)){
            result = 0;
        }
        return result;
    }
};

int main(){
    int a[10] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    int len = 9;
    vector<int> numbers;
    Solution ss;

    for(int i=0; i < len; i++){
        numbers.push_back(a[i]);
    }
    cout<<ss.MoreThanHalfNum_Solution(numbers)<<endl;
}

• 思路二、基于数组特点找出时间复杂度为 O(n) 的算法
  1、数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数的和还要多。因此，我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。
  ２、当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加１；如果下一个数字和我们之前保存的数字不同，则次数减１；如果次数为０，那么我们需要保存下一个数字，并把次数设为１．
  ３、由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为１时对应的而数字

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool checkVality(vector<int> numbers, int result){
        bool vality = true;
        int times = 0;
        for(int i=0; i < numbers.size(); i++){
            if(result == numbers[i]){
                times ++;
            }
        }

        if(times * 2 <= numbers.size()){
            vality = false;
        }
        return vality;
    }

    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size() == 0){
            return 0;
        }

        int times = 1;
        int result = numbers[0];
        for(int i=1; i < numbers.size(); i++){
            if(times == 0){
                result = numbers[i];
                times = 1;
            }
            else if(result == numbers[i]){
                times ++;
            }
            else{
                times --;
            }
        }

        if(!checkVality(numbers, result)){
            result = 0;
        }
        return result;
    }
};

int main(){
    int a[10] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    int len = 9;
    vector<int> numbers;
    Solution ss;

    for(int i=0; i < len; i++){
        numbers.push_back(a[i]);
    }

    cout<<ss.MoreThanHalfNum_Solution(numbers)<<endl;
}

总结展望

• 有快排的思想在其中，题目很好，值得反复思考