多数元素(Majority Element)

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

int majorityElement(int* nums, int numsSize){
    while (true){
        int i = rand() % numsSize;
        int count = 0;
        for(int j =0 ; j<numsSize; j++){
            if(nums[j] == nums[i]){
                count++;
            }
        }
        if (count > numsSize/2){
            return nums[i];
        }
    }
    return 0;
}

因为有一半以上的概率获得的数字是占一半以上的元素，效率难以评估

int cmp(const void* a, const void* b){
    return *(int *)a- *(int *)b;
}

int majorityElement(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    return nums[numsSize/2];
}

看到这个题目，应该可以很自然的想到哈希表，但是C本身不自带，手动实现Hash表

struct Entry {
    int num;
    int count;
};

void addOne(struct Entry *countMap, int num, int hashTableSize) {
    int hash = (num % hashTableSize + hashTableSize) % hashTableSize;
    while (true) {
        if (countMap[hash].count == 0){
            countMap[hash].num = num;
            countMap[hash].count++;
            return;
        }
        if (countMap[hash].num == num){
            countMap[hash].count++;
            return;
        }
        hash = (hash + 1) % hashTableSize;
    }
}

int majorityElement(int* nums, int numsSize){
    int hashTableSize = numsSize * 2;

    struct Entry countMap[hashTableSize];
    for (int i =0; i<hashTableSize; i++){
        countMap[i].count = 0;
    }
    for (int i = 0; i < numsSize; ++i) {
        addOne(countMap, nums[i], hashTableSize);
    }
    for (int i = 0; i < hashTableSize; ++i) {
        if (countMap[i].count > numsSize/2){
            return countMap[i].num;
        }
    }
    return 0;
}

int rangedMajorityElement(int* nums, int start, int stop){
    if(start == stop) return nums[start];
    int mid = start +(stop - start) /2;
    int leftMajorityElement = rangedMajorityElement(nums, start, mid);
    int rightMajorityElement = rangedMajorityElement(nums, mid+1, stop);

    if (leftMajorityElement == rightMajorityElement){
        return leftMajorityElement;
    }

    int leftCount = 0;
    for (int i = start; i <= stop; ++i) {
        if (nums[i] == leftMajorityElement){
            leftCount++;
        }
    }
    int rightCount = 0;
    for (int i = start; i <= stop; ++i) {
        if (nums[i] == rightMajorityElement){
            rightCount++;
        }
    }

    return leftCount>rightCount?leftMajorityElement:rightMajorityElement;
}

int majorityElement(int* nums, int numsSize){
    return rangedMajorityElement(nums, 0, numsSize-1);
}

分治法

int majorityElement(int* nums, int numsSize){
    int num;
    int count = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (count == 0){
            num = nums[i];
            count = 1;
        } else if (num == nums[i]){
            count ++;
        } else{
            count --;
        }
    }
    return num;
}

太强了，这个做法