讨论/《排序算法全解析》 - 解析/
《排序算法全解析》 - 解析
共 11 个回复
class Solution {
    public int majorityElement(int[] nums) {
        int can=0,count=0;
        for(int num:nums){
            if(count==0)can=num;
            if(num==can)count++;
            else count--;
        }
        return can;
    }
}
6

思路的关键点应该是元素出现最多的次数大于总数组长度的一半,
也就是可以理解为假设 数组中 8 这个字符出现的次数最多,同时意味着他出现的次数减去其他所有数字出现的次数,还要至少要多一个。
比如 【8,8,8,8,7,7,7】 3个8和3个7 抵消了 还剩下一个8.
同理 【8,8,8,8,5,6,7】 3个8和5,6,7抵消了 还剩下8.

2

感觉快排取中间数和摩尔投票法的思想都很秀,一比较,真的没法下手写哈希表,学习一手٩( 'ω' )و get!

def majorityElement(nums):
    """
    摩尔投票法
    """
    count = 1
    val = nums[0]
    for i in range(1, len(nums)):
        if nums[i] == val:
            count += 1
        else:
            if count > 0:
                count -= 1
            else:
                val = nums[i]
                count = 1
    return val
2

这题,正常人谁用快排??

2

投票算法,因为题目给了必然有大于一半的数字,想成每个人在投票

1

emmm个人觉得这道题放在快排下作为例子不合适,这道题重点是O(n)的几种解法

1
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int vote = 0, res;

        for (int num: nums) {
            if (vote == 0) res = num;
            vote += (res == num) ? 1:-1;
        }
        return res;
    }
};
1

有取巧成分,思路是:总是存在多数元素,注意这个"总是"两个字,总是存在说明至少有一个元素过半,要不是因为总是存在,快排就不适用了。

审题不仔细,谢了。 没注意到“一半”,我以为是求众数。 XD

能讲讲具体思路么?