【数学专题】剑指 Offer 39. 数组中出现次数超过一半的数字-跟着帅地玩副业，开拓第二曲线PlayOffer

sc_Yang 普通 2023年9月11日上午7:56

class Solution {
public:
    // 法1:使用哈希表进行存储之后对元素的个数进行判断
    int majorityElement_hash(vector<int>& nums) {
        unordered_map<int , int> counts;
        int majority = 0;
        int curCount = 0;
        for(int num : nums){
            counts[num]++;
            if(counts[num]>curCount){
                majority = num;
                curCount = counts[num];
            }
        }
        return majority;
    }
    // 法2:先排序，然后取中位数，则必然时所求值
    int majorityElement(vector<int>& nums){
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月7日下午10:01

class Solution {
    //投票法:时间复杂度为O(N),空间复杂度为O(1)
    //另外解法:排序、有序哈希表
    public int majorityElement(int[] nums) {
        int res = nums[0], count = 1;
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] != res) {
                count --;
                if (count == 0) {
                    res = nums[i];
                    count ++;
                }
            } else {
                count ++;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月7日上午11:24

思路：1、排序后取中间，长度超过一半的数，中间肯定就是结果；2、投票法，众数票数+1，非众数票数-1，如果票数为0那么众数非众数各占一半，剩下的子数组众数还是它，通过不断缩小范围，最后的结果即为众数
复杂度：1、时间复杂度O(logn)，空间复杂度O(1)；2、时间复杂度O(n)，空间复杂度O(1)

// 排序
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int mid = (right - left) / 2 + left;
        return nums[mid];
    }
}
// 投票
class Solution {
    public int majorityElement(int[] nums) {
        int vote = 0;
        int most = 0;
        for (int num : nums) {// 循环缩小区间
            if (vote == 0) {
                most = num;// 票数为0，将众数设置为当前num
            }
            vote += num == most ? 1 : -1;// 众数为当前num，票数+1，否则票数-1
        }
        return most;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月4日下午10:40

1、哈希map

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i< nums.length; i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i])+1);
            }else{
                map.put(nums[i], 1);
            }
            if(map.get(nums[i]) > nums.length/2){
                return nums[i];
            }
        }
        return 0;
    }
}

2、摩尔投票

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int x = -1, cnt = 0;
        for(int item : nums){
            if(cnt == 0){
                x = item;
                cnt = 1;
            }else{
                cnt += x==item? 1:-1;
            }
        }
        cnt = 0;
        for(int item : nums){
            if(x == item){
                cnt++;
            }
        }
        return cnt > n/2 ? x:0;
    }
}

0 赞同 0 条回复

c 普通 2023年9月3日下午8:42

排序去中间值学习题解投票

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int res=0;;
        for(int i = 0;i<nums.length;i++){
            if(count==0){
                res = nums[i];
            }
            count+=(nums[i]==res)?1:-1;
        }
        return res;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月3日下午3:07

// 投票法，时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 1;
        int tmp = nums[0];
        for(int i=0;i<nums.size();++i)
        {
            if(tmp==nums[i]) ++count;
            else --count;
            if(count == 0)
            {
                tmp = nums[i];
                count=1;
            }
    }
    return tmp;}
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月3日下午3:05

使用了哈希法。不过最佳方法是投票法

class Solution {
    public int majorityElement(int[] nums) {
        //哈希法
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        int res = 0;
        for(Integer k : map.keySet()) {
            if (map.get(k) > nums.length / 2) {
                res = k;
                break;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

JustRtn 普通 2023年9月3日下午2:26

两两比较，不同则消除，最后剩下的就是众数；
时间复杂度O(n),空间复杂度O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.size() < 3) {
            return nums[0];
        }

        int m = nums[0];
        int count = 1;
        for (int i = 1; i < nums.size(); i++) {
            if(nums[i] == m) {
                count++;
            } else if (--count == 0) {
                m = nums[i];
                count = 1;
            }
        }
        return m;
    }
};

0 赞同 0 条回复

【数学专题】剑指 Offer 39. 数组中出现次数超过一半的数字

共以下 8 个回答

# 回答此问题取消回复

【数学专题】剑指 Offer 39. 数组中出现次数超过一半的数字

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复