leetcode169 169. 多数元素 随机法,投票法

tech2022-07-15  170

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

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

 

示例 1:

输入: [3,2,3] 输出: 3 示例 2:

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

 

 

随机法:rand确定一个数,数数。    空间(1) 时间很有可能0(∞)

投票法:for遍历,把当前值赋值给a。之后碰到相同值,b+1.不同则b-1。如果b小于0了,则让该位置的数复制给a。重新计算

class Solution {

public:

    int majorityElement(vector<int>& nums) {

        int candidate = -1;

        int count = 0;

        for (int num : nums) {

            if (num == candidate)

                ++count;

            else if (--count < 0) {

                candidate = num;

                count = 1;

            }

        }

        return candidate;

    }

};

 

最新回复(0)