剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制:

1 <= 数组长度 <= 50000

注意:本题与主站 169 题相同:https://leetcode-cn.com/problems/majority-element/

解决方案

该数字必然是数组的中位数,所以可以使用快排的partition函数,直到分界正好是数组中间。

class Solution {

    private int[] array;

    public int majorityElement(int[] nums) {
        array = nums;
        int begin = 0, end = nums.length - 1;
        int middle = (begin + end) >> 1;

        int index = partition(begin, end);
        while (index != middle) {
            if (index < middle) {
                begin = index + 1;
            } else if (index > middle) {
                end = index - 1;
            }
            index = partition(begin, end);
        }

        return nums[index];
    }

    private int partition(int begin, int end) {
        int pivot = array[begin];
        int ptr1 = begin, ptr2 = end;

        while (ptr1 < ptr2) {
            while (ptr1 < ptr2 && array[ptr2] >= pivot) {
                ptr2 -= 1;
            }
            while (ptr1 < ptr2 && array[ptr1] <= pivot) {
                ptr1 += 1;
            }
            if (ptr1 < ptr2) {
                int tmp = array[ptr1];
                array[ptr1] = array[ptr2];
                array[ptr2] = tmp;
            }
        }

        array[begin] = array[ptr1];
        array[ptr1] = pivot;

        return ptr1;
    }

}

摩尔投票法。参见如何理解摩尔投票算法? – 知乎用户的回答 – 知乎

class Solution {

    private int[] array;

    public int majorityElement(int[] nums) {
        int modeAssumed = nums[0], vote = 0;
        for (int num : nums) {
            if (vote == 0) {
                modeAssumed = num;
            }
            vote += (num == modeAssumed ? 1 : -1);
        }
        return modeAssumed;
    }

}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据