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

June 普通 2023年9月7日下午10:37

class Solution {
    public int majorityElement(int[] nums) {
        int num = nums[0];
        int cnt = 1;
        for (int i=1;i<nums.length;i++)
        { // 凡是遇到和当前次数最多的数字不同的数字，cnt就减一
            if (num == nums[i])
            {
                cnt++;
            }
            else if(cnt == 0 && num != nums[i])
            {
                num = nums[i];
                cnt++;
            }
            else
            {
                cnt--;
            }
            if (cnt == 0)
                num = nums[i];
        }
        return num;
    }
}

0 赞同 0 条回复

hi 普通 2023年8月22日上午8:57

记录数的出现次数，最后存在的一定是出现次数最多的那个数
数不同时，次数减一，相同加一，减到了0，记录下一个新的数的次数

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt = 0, val = -1; //val 是随便赋值的
        for(int x : nums){
            if(cnt == 0) val = x, cnt ++;
            else{
                if(val == x) cnt ++;
                else cnt--;
            }
        }
        return val;
    }
};

0 赞同 0 条回复

普通 2023年8月7日下午11:22

c++ 代码哈希表
class Solution {
public:
int majorityElement(vector& nums) {
map<int,int> cu;
int r=0;
for(int i=0;i<nums.size();i++)
{
cu[nums[i]]++;
if( cu[nums[i]]>nums.size()/2)
return nums[i];
}
return r;
}
};

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年8月6日下午8:19

代码

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length<2) return nums[0];
        int x = nums[0];
        int sum = 1;
        for(int i=1;i<nums.length;i++){
            if(sum==0){
                x = nums[i];
                sum = 1;
            }else{
                if(x==nums[i]){
                    sum++;
                }else{
                    sum--;
                }
            }
        }
        return x;
    }
}

0 赞同 0 条回复

艺普通 2023年8月5日下午4:35

“`c++
//时间O(n)，空间O(n/2)
//哈希表
class Solution {
public:
int majorityElement(vector& nums) {
unordered_map hash;
int res = 0, n = nums.size();
for(int i = 0; i n/2)
res = nums[i];
}
return res;
}
};

0 赞同 0 条回复

北辰普通 2023年8月4日下午4:30

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int num = nums[0];
        int cnt = 1;
        for(int i=1;i<n;i++) {
            if(nums[i]!=num) {
                if(cnt>0) {
                    cnt--;
                }else {
                    num = nums[i];
                    cnt = 1;
                }
            }else {
                cnt++;
            }
        }
        return num;
    }
}

more投票法

0 赞同 0 条回复

#00456B 普通 2023年8月2日下午11:31

class Solution {
public:
    //时间空间都O(n)
    // int majorityElement(vector<int>& nums) {
    //     int n = nums.size();
    //     unordered_map<int,int> umap;
    //     for(int x:nums){
    //         umap[x]++;
    //         if(umap[x] > n/2){
    //             return x;
    //         }
    //     }
    //     return -1;
    // }
    int majorityElement(vector<int>& nums) {
        //投票法
        int target = 0;
        int count = 0;
        for(int x:nums){
            if(count == 0){//要么刚开始，要么前面的数都正负抵消了
                target = x;
                count = 1;
            }
            else if(x == target){//是当前的众数，++
                count++;
            }
            else{//不是当前的众数，--
                count--;
            }
        }
        return target;
    }
};

0 赞同 0 条回复

Mby 普通 2023年8月2日下午8:10

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length <= 2){
            return nums[0];
        }
        int x = nums[0];
        int sum = 1;//摩尔投票法

        for(int i = 1; i < nums.length; i++){
            if(sum == 0){
                x = nums[i];
                sum = 1;
            }else {
                if(x == nums[i]){
                    sum++;
                }else{
                    sum--;
                }
            }
        }
        return x;
        //时间复杂度：O(n)
        //空间复杂度：O(1);
    }
}

0 赞同 0 条回复

CKX 普通 2023年8月2日下午6:06

func majorityElement(nums []int) int {
    //众数
    target := 0
    //计数器
    count := 0

    for i := 0; i < len(nums); i++ {
        if count == 0 {
            //计数器为0，假设该数为众数
            target = nums[i]
            //众数出现一次
            count = 1
        } else if nums[i] == target {
            count++
        } else {
            count--
        }
    }
    return target
}

时间O(n)
空间O(1)

0 赞同 0 条回复

Marshan 普通 2023年8月2日下午3:24

暴力

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int length = nums.size();
        return nums[int(length/2)];
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年7月31日下午6:19

class Solution {
public int majorityElement(int[] nums) {
//超过一般可以用一个变量记录值和出现次数这个数出现一半和出现一次的抵消最后剩的肯定是他
int result =nums[0];
int count =1;
for(int i=1;i<nums.length;i++)
{
if(nums[i]result)
{
count++;
}else
{
count–;
}
if(count0)
{
result=nums[i];
count++;
}
}
return result;
}
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月30日下午9:55

摩尔计数法

function majorityElement(nums: number[]): number {
    let vote = 0, val = 0;
    for (let num of nums) {
        if (vote === 0) val = num;
        vote += (num === val ? 1 : -1);
    }
    return val;
};

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月30日下午9:29

class Solution {
    public int majorityElement(int[] nums) {
        // 寻找“众数”
        // 哈希表 O(n) O(1)
        // 排序法，中位数一定是众数 O(nlogn) O(1)
        // 摩尔投票法：票数正负抵消 O(n) O(1)
        // 众数的票 > 其他数票之和
        // 假设众数是第一个数
        int x = nums[0];
        int sum = 1;
        for(int i=1;i<nums.length;i++){
            if(sum == 0){
                // sum = 0时，需要换一个数作为众数
                x = nums[i];
                sum = 1;
            } else{
                if(x!=nums[i]) sum--;
                else sum++;
            }
        }
        return x;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Luminous 普通 2023年7月30日上午10:46

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == res){
                count++;
            }else{
                count--;
                if(count <= 0){
                    res = nums[i];
                    count = 1;
                }
            }
        }
        return res;
    }
}
时间复杂度：O(n)

以上是代码

0 赞同 0 条回复

阿尚普通 2023年7月29日下午11:24

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == res){
                count++;
            }else{
                count--;
                if(count <= 0){
                    res = nums[i];
                    count = 1;
                }
            }
        }
        return res;
    }
}
时间复杂度：O(n)

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月29日下午7:16

7.29
Day20：下面是代码

class Solution {
    public int majorityElement(int[] nums) {
        //摩尔投票法
        int cand_num = nums[0], count = 1;
        for(int i = 1; i < nums.length; i++){
            if(cand_num == nums[i]) count++;
            else if(count-- == 0){
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月29日下午5:22

消消乐，前后数不同就计数-1，反之就+1

class Solution {
    public int majorityElement(int[] nums) {
        int res = 0, cnt = 0;
        for(int i = 0; i < nums.length; i ++) {
            if(cnt == 0) {
                res = nums[i];
                cnt ++;
            } else {
                if(res == nums[i]) cnt ++;
                else cnt --;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月29日下午4:44

public int majorityElement(int[] nums) {
        // 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
        //输出: 2
        int count = nums.length / 2;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer orDefault = map.getOrDefault(num, 0);
            map.put(num, orDefault+1);
        }
        for (Integer key : map.keySet()) {
            Integer value = map.get(key);
            if (value > count) {
                return key;
            }
        }
        return -1;
    }

0 赞同 0 条回复

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

共以下 18 个回答

# 回答此问题取消回复

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

共以下 18 个回答

# 回答此问题 取消回复

# 回答此问题取消回复