Java-LeetCode169. 多数元素-多数投票算法 | 快速排序思想

• 算法
  • 1.多数投票算法
  • 2.出现次数超过一半的数字则超过其他所有数字出现次数之和
  • 3.保存两个变量，result和times，遍历数组
    • 如果当前数字等于result，times加一
    • 如果当前数字不等于result，且times不等于0，times减一
    • 如果当前数字不等于result，且times等于0，置result为当前数字，times为1

public int majorityElement(int[] nums) {
    // checkArguments(nums);

    int result = nums[0];
    int times = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == result) {
            times++;
        } else {
            if (times > 0) {
                times--;
            } else {
                result = nums[i];
                times = 1;
            }
        }
    }
    return result;
}

• 算法
  • 1.快速排序算法
  • 2.出现次数超过一半的数字排序后一定位于mid位置
  • 3.使用快排的partition迭代寻找mid位置的数字

public int majorityElement(int[] nums) {
    // checkArguments(nums);

    int start = 0, end = nums.length - 1, mid = nums.length >> 1;
    int index = partition(nums, start, end);
    while (index != mid) {
        if (index > mid) {
            end = index - 1;
        } else {
            start = index + 1;
        }
        index = partition(nums, start, end);
    }
    return nums[index];
}

private int partition(int[] nums, int start, int end) {
    int index = new Random().nextInt(end-start+1) + start;
    swap(nums, end, index);
    int small = start - 1;
    for (index = start; index < end; index++) {
        if (nums[index] < nums[end]) {
            small++;
            if (small != index) {
                swap(nums, small, index);
            }
        }
    }
    swap(nums, ++small, end);
    return small;
}

private void swap(int[] nums, int start, int end) {
    int temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
}