✌粤嵌—2024/3/20—多数元素

代码实现：

方法一：因为多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素，所以对元素排序后，n/2一定是多数元素——超时

// 交换
void swap(int *m, int *n) {
    int temp = *m;
    *m = *n;
    *n = temp;
}

// 快速排序
// 左闭右开  l:左边第一个待排序元素下标  r:待排序元素个数
void quick_sort(int *arr, int l, int r) {
    if (r - l <= 2) {
        if (r - l <= 1) { // 没有或者只剩下一个
            return;
        }
        if (arr[l] > arr[r - 1]) { // 剩下两个
            swap(&arr[l], &arr[r - 1]);
        }
        return;
    }
    int i = l; // 左臂  下标
    int j = r - 1; // 右臂  下标
    int pivot = arr[i]; // 记录轴
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[i] = pivot;
    quick_sort(arr, l, i); // 左边递归
    quick_sort(arr, i + 1, r); // 右边递归
}

int majorityElement(int *nums, int numsSize) {
    quick_sort(nums, 0, numsSize);
    return nums[numsSize / 2];
}

方法二：摩尔投票法

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