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

Gg 普通 2023年5月2日下午9:10

class Solution {
    // 摩尔投票法。先取一个候选人，与候选人相同+1，不相同-1。
    // sum为0 可以重新选人
    public int majorityElement(int[] nums) {
        // 定义候选人
        int candidate = 0;
        int sum = 0;
        for(int num : nums){
            // 重新选人
            if(sum == 0){
                candidate = num;
            }
            sum += candidate == num ? +1:-1;
        }
        return candidate;
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月15日上午11:07

互相消耗或者排序

class Solution {
    public int majorityElement(int[] nums) {
        // Arrays.sort(nums);
        // return nums[nums.length / 2];
        //出现次数超过一半，一个其他数字，一个这个数，移除最后剩下的就是。
        int k = 0;
        int cur = 0;
        for(int i = 0; i < nums.length; i++){
            if(k == 0){
                cur = nums[i];
                k++;
            }else{
                if(cur == nums[i]){
                    k++;
                }else{
                    k--;
                }
            }  
        }
        return cur;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月12日下午4:27

def majorityElement(nums):
# 摩尔投票法
    if len(nums) == 1:
        return nums[0]

    # 假设数字的第一个数是众数
    n = nums[0]
    # 众数的个数sum
    sum = 1
    for _ in nums[1:]:
        # 如果众数的个数为零，说明之前已经全部抵消完了，需要重新规定众数，就将当前值做为众数
        if sum == 0:
            n = _
            sum = 1
        # 如果当前数等于众数
        else:
            if _ == n:
                sum += 1
            else:
                sum -= 1
    return n

0 赞同 0 条回复

lucca 普通 2023年1月11日下午11:22

摩尔投票法

被投票元素的票数为0，则淘汰，换下一个元素作为被投票的元素
目前数字和被投票元素相同，投票+1
不同，票数-1
如果是非众数，一定会出现投票为0被替换的那一天，因为有超过一半的众数会投反对票
如果是众数，可能中间某一次票数为0被替换，但最终不会有任何非众数的票数超过它
如果前n个数里，一半是众数，一半不是众数（众数投票为0），则剩下的数组，众数仍然不变
时间复杂度：O(N)
空间复杂度：O(1)

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0, x = 0;
        for (int num : nums) {
            if (cnt == 0) x = num;
            if (x == num) cnt++;
            else cnt--;
        }
        return x;
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年12月6日下午11:53

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

# 摩尔投票法
        candidate = None
        count = 0

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)
        return candidate

0 赞同 0 条回复

xye 普通 2022年12月6日下午12:06

func majorityElement(nums []int) int {
    x, vote := 0, 0
    for _, i := range nums {
        if vote == 0 {
            x = i
        }
        if x == i {
            vote++
        }else{
            vote--
        }
    }
    return x
}

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

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:24

func majorityElement(nums []int) int {
    x,vote:=nums[0],1     //初始多数元素为第一个元素，票为1
    for i:=1;i<len(nums);i++{
        if vote==0{      //票数为0时就等于下一个元素
            x=nums[i]
        }
        if nums[i]==x{   //相等就得票数增加
            vote++
        } else{
            vote--      //不相等就减
        }
    }
    return x    //返回得票数最多的元素
}

func majorityElement(nums []int) int {
   num:=sort.IntSlice(nums) //排序
   sort.Sort(num)
   return num[len(num)/2]  //返回
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:28

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> m1;
        int mid = nums.size()/2;
        for(auto c:nums){
            m1[c]++;
            if(m1[c] > mid) return c; //使用map存储出现次数
        }
        return -1;

    }
};

0 赞同 0 条回复

庄重普通 2022年11月26日下午10:03

// 思路1；哈希表--非最优解-->时间复杂度O(n)
//     1.遍历数组，哈希表记录数字出现的次数
//     2.遍历哈希表，找到次数大于n/2的值
// 思路2：排序求解--非最优解-->时间复杂度O(nlogn)
//     1.排序后，中位数为题目要求找的众数
// 思路3：摩尔投票--最优解
//     1.循环遍历数组，不一样的相互抵消，众数最多，sum对应的结果x为众数值
//     2.即便x记录的不是众数（x被抵消了，最终还是众数最多），也不会影响最终结果为众数值
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //特殊情况
        if(nums.size() < 3){
            return nums[0];
        }
        //x记录当前数，最终返回结果为众数
        int x = nums[0];
        //出现一次x加1，不一样的减1
        int sum = 0;
        for(int i = 0; i < nums.size(); ++i){
            if(sum == 0){
                x = nums[i];
                sum = 1;
            }
            else{
                if(nums[i] == x){
                    ++sum;
                }
                else{
                    --sum;
                }
            }
        }

        return x;
    }
};
//时间复杂度O(n)
//空间复杂度O(1)

0 赞同 0 条回复

云雾里普通 2022年11月20日下午1:40

//排序+统计
public int majorityElement(int[] nums) {
        int length = nums.length;
        if(length==1){
            return nums[0];
        }
        int midSum = length/2;
        Arrays.sort(nums);
        int sum=1;
        for (int i = 0; i < nums.length-1; i++) {
            if(nums[i]==nums[i+1]){
                sum++;
                if(sum>midSum){
                    return nums[i];
                }
            }else {
                sum=1;
            }
        }
        return -1;
    }

0 赞同 0 条回复

lobort 普通 2022年11月19日下午4:44

class Solution {
    public int majorityElement(int[] nums) {
        //方法一： 直接排序返回中间值
        Arrays.sort(nums);
        return nums[nums.length >> 1];

        //方法二  投票  众数记为1  其他数记为-1  逐个相加
        int sum = 0;
        int res = 0;
        for(int num : nums){
            if(sum == 0){
                res = num;
            }
            //相等就加1 不等就-1
            sum += num == res ? 1 : -1;
        }
        return res; 
    }
}

方法一简单粗暴时间 O(logn) 空间 0
方法二摩尔投票时间O(n) 空间O(n)

0 赞同 0 条回复

你有点可爱喔普通 2022年11月18日下午1:55

时间复杂度 O(N)空间复杂度 O(1)
有个方法测试用例不通过

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

        return result;
    }
}

0 赞同 0 条回复

@ 普通 2022年11月17日下午9:20

思路：哈希或摩尔投票法

class Solution {

    //哈希
    //时间复杂度 O(N)
    //空间复杂度 O(N) 
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int l = nums.length / 2;
        int res = 0;

        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]) > l){
                res = map.get(nums[i]);
                break;
            }

        }

        return res;

    }

    //摩尔投票法
    //时间复杂度 O(N)
    //空间复杂度 O(1) 
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }

}

0 赞同 0 条回复

是梦终空永久会员 2022年11月17日上午2:21

哈希和排序就不写了，直接写投票了
时间O(n)
空间O(1)

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

0 赞同 0 条回复

y 普通 2022年11月16日下午11:57

var majorityElement = function(nums) {
  if (nums.length === 0) return null;
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
      let cur = nums[i];
      if (map.has(cur)) {
          map.set(cur, map.get(cur) + 1);
      } else {
          map.set(cur, 1);
      }
  }
  let mid = nums.length / 2;
  for([key, value] of map) {
     if( value > mid) {
         return key;
     }
  }
};

将每个元素出现的次数存在哈希表，最后遍历哈希表找出次数大于n/2的元素

0 赞同 0 条回复

天然普通 2022年11月16日下午7:42

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n,i=0,0
        for num in nums:
            if i==0: n = num
            if n==num:
                i+=1
            if n!=num:
                i-=1

        return n
#时间复杂度为O（n），空间复杂度O(1)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月16日下午2:56

时间复杂度为O（n），空间复杂度O(1)

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

0 赞同 0 条回复

just 普通 2022年11月16日上午10:25

//投票‘
class Solution {
public:
int majorityElement(vector& nums) {
int res=nums[0],cnt=1;
for(int i=1;i<nums.size();++i){
if(nums[i]res) cnt++;
else{
cnt–;
if(cnt<0){
cnt=1;
res=nums[i];
}
}
}
return res;

};

0 赞同 0 条回复

Error 普通 2022年11月15日下午10:07

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        v = 0
        i = 0
        for n in nums:
            if i == 0:
                v = n
            if n != v:
                i -= 1
            else:
                i += 1
        return v

时间复杂度 O(n)

0 赞同 0 条回复

So 普通 2022年11月15日下午3:41

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 条回复

派大星普通 2022年11月15日上午11:39

class Solution {
//使用map集合来遍历
//时间复杂度O(n)
//空间复杂度O(1)
    public int majorityElement(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        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);
            }
        }
        int i = -1;
        int num = 0;
        for (Integer integer : map.keySet()) {
            if(map.get(integer) > num){
                i = integer;
                num = map.get(integer);
            }
        }
        return i;

    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月14日下午10:05

    public int majorityElement(int[] nums) {

        //时间复杂度O(n)
        //空间复杂度O(1)
        //思路使用摩尔投票法
        //步骤
        // 定义一个最终获胜者
        // 不同的数字之间可以相互抵消
        // 如果当前胜利者存在多个， 可以抵消一个当前数
        //如果两个数字都抵消为0  则下一个数字是最终胜出者
        int cut =1;
        int ans = nums[0];//先默认找出一个
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==ans){
                //等于上一个数的继续计数
                cut++;
            }else if(--cut==0){
                //不等于，则抵消，抵消到0 的时候重新赋值
                ans=nums[i];
                cut=1;
            }
        }
        return ans;

        //其他方法 hash计数 时间复杂度 空间复杂度都是O(n)
        //排序也是Olg(n)
    }

0 赞同 1 条回复

just 普通 @ 波波_1936 2022年11月15日下午12:53
//投票法
class Solution {
public:
int majorityElement(vector& nums) {
int res=nums[0],cnt=1;
for(int i=1;i<nums.size();++i){
if(nums[i]res) cnt++;
else{
cnt–;
if(cnt<0){
cnt=1;
res=nums[i];
}
}
}
return res;
```
}
```
};
登录以回复

訁訁訁訁訁普通 2022年11月14日下午9:52

时间复杂度O(nlogn) 空间复杂度O(1)

//个数超过一半，排序必定在中间
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

哈希表时间复杂度O(N)空间复杂度O(n/2)

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

//摩尔投票法，因为相同元素大于整个数组长度的一半，所以采用一换一的形式，最后剩余的一定是该元素
//时间复杂度O(N)空间复杂度O(1)
class Solution {
    public int majorityElement(int[] nums) {
       int res = 0,count = 0;
       for(int i = 0;i < nums.length;i++){
           if(count == 0){
               res = nums[i];
               count++;
           }else{
               count += res == nums[i] ? 1 : -1;
           }
       }
       // 1 2 3 2 2 4 2
       /**
    count 1 0 1 0 1 0 1
      res 1 1 3 3 2 2 2
        */
       return res;
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月14日下午9:52

摩尔投票

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0;
        int sum = 0;
        for(int num : nums) {
            if(sum == 0) {
                x = num;
            }
            sum = sum + (num == x ? 1 : -1);
        }
        return x;
    }
}

0 赞同 0 条回复

青木普通 2022年11月14日下午8:58

/**
    由于超过了一半，因此可以直接进行计数，
    用cnt记录当前相同数字的数量，当访问的数不同于cur，则cnt--

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

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        int cur = 0xffffffff;
        for(int num : nums){
            if(num == cur){
                cnt += 1;
            }
            else if(cnt == 0){
                cnt += 1;
                cur = num;
            }
            else{
                cnt -= 1;
            }

        }
        return cur;
    }
}

0 赞同 0 条回复

T 普通 2022年11月14日下午8:18

class Solution {
    //摩尔投票法
    public int majorityElement(int[] nums) {
        int votes = 0, res = 0;
        for(int num : nums) {
            if(votes == 0) res = num;
            votes += res == num ? 1 : -1;
        }
        return res;
    }
}

0 赞同 0 条回复

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

共以下 26 个回答

摩尔投票法

# 回答此问题取消回复

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

共以下 26 个回答

摩尔投票法

# 回答此问题 取消回复

# 回答此问题取消回复