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

kfaebot 普通 2024年3月27日下午4:41

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int vote=0;
        int id=0;
        //遍历每个商品
        for(int i=0;i<stock.size();i++){
            if(vote==0){
                id=stock[i];
            }
            if(stock[i]==id){
                vote++;
            }
            else{
                vote--;
            }
        }
        return id;
    }
};

0 赞同 0 条回复

一个达不刘普通 2024年3月25日上午10:19

class Solution {
public:
//数量超出stock.length/2, 那么排序后，中间元素是所求id。
int inventoryManagement(vector& stock) {
sort(stock.begin(),stock.end());

    int n = m/2;
    return stock[n];
}

};

0 赞同 0 条回复

言之命至普通 2024年3月24日下午8:59

每个数开始时的票数votes=1，如果下一个数等于当前数，则votes++, 否则votes–.最后留下的一定是众数。

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

神经蛙普通 2024年3月24日下午7:20

class Solution {
public:
int inventoryManagement(vector& stock) {
int x = stock[0];
int votes = 0;
for(int num :　stock){
if(votes 0) x = num;
if(num x )
{
votes += 1;
}
else
{
votes -= 1;
}
}
return x;
}
};
时间复杂度O（n），空间复杂度O(1)

0 赞同 0 条回复

Jimmy 普通 2024年3月24日下午1:49

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

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int votes = 0;//出现了==x就投票+1，否则就-1，因为最终要找的结果出现的频次大于一半，如果x符合这个条件的话votes最终是不可能小于0的
        int x = 0;//结果
        for(int i=0;i<stock.size();i++){
            if(votes == 0){
                x = stock[i];
            }
            if(stock[i] == x){
                votes++;
            }else{
                votes--;
            }
        }
        return x;
    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月24日上午11:14

class Solution {
    public int inventoryManagement(int[] stock) {
        if(stock.length<=2) return stock[0];

        int sum=1;
        int x=stock[0];

        for(int i=1;i<stock.length;i++){
            if(sum==0){
                x=stock[i];
                sum=1;
            }else{
                if(stock[i]==x){
                    sum++;
                }else{
                    sum--;
                }
            }
        }

        return x;
    }
}

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月23日下午10:56

时间复杂度O(n)
空间复杂度O(1)
摩尔投票法

“`C++
class Solution {
public:
int inventoryManagement(vector& stock) {
if(stock.size() < 3) { return stock[0]; } //摩尔投票，边界条件 int sum = 0; int x; for(int i = 0; i < stock.size(); i++) { if(sum == 0) { x = stock[i]; sum++; } else { if(x == stock[i]) { sum++; } else { sum--; } } } return x; } }; ```

0 赞同 0 条回复

云无深雁影普通 2024年3月23日下午10:34

class Solution {
public int inventoryManagement(int[] stock) {
int curNum = stock[0];
int count = 1;
for(int i = 1; i < stock.length; i++){
if(stock[i] != curNum)
count–;
else
count++;
if(count < 0){
count = -count;
curNum = stock[i];
}
}
return curNum;

}
//时间复杂On

//空间O1

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月23日下午8:10

打卡

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int cnt = 0;
        int res = 0;
        for(int i = 0; i < stock.size(); ++i) {
            if(cnt == 0) {
                res = stock[i];
                cnt++;
            } else {
                if(res == stock[i]) cnt++;
                else cnt--;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

方铎码农普通 2024年3月23日下午7:12

class Solution {
    // 在一个集合中，如果一个元素的出现次数比其他所有元素的出现次数之和还多，那么就称它为这个集合的绝对众数。等价地说，绝对众数的出现次数大于总元素数的一半
    // 摩尔投票法，当一个数的数量大过其它数的总和，那么它一定是该数组的数的绝对多数
    public int inventoryManagement(int[] stock) {
        if(stock.length <= 2) return stock[0];
        int x = stock[0];
        int cnt = 1;
        for (int i = 1; i < stock.length; i++){
            if(stock[i] == x) cnt++;
            else {
                cnt--;
                if(cnt == 0){
                    x = stock[i];
                    cnt = 1;
                }
            }
        }
        return x;
    }
}

时间复杂度$O(n)$，空间复杂度$O(1)$

0 赞同 0 条回复

Yox 普通 2024年3月23日上午2:37

class Solution:
def inventoryManagement(self, stock: List[int]) -> int:
votes, count= 0,0
for num in stock:
if votes 0: x= num
if num x: votes += 1
else: votes-=1
for num in stock:
if num x:count +=1
return x if count>len(stock)//2 else 0
时间o n 空间 o 1

0 赞同 0 条回复

Raphtalia. 普通 2024年3月22日下午11:58

class Solution {
public:
int inventoryManagement(vector& stock) {
int flag = 1;
if(stock.size() 1) return stock[0];
int x = stock[0];
for(int i = 1; i < stock.size(); i ++) {
if(x stock[i]) flag ++;
else flag –;
if(flag 0) {
if(i < stock.size() – 1) {
x = stock[i + 1];
}
continue;
}
}
return x;
}
};时间复杂度O（n），空间复杂度O（1）

0 赞同 0 条回复

mpweixin用户普通 2024年3月22日下午9:56

java
class Solution{
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 条回复

紫芝普通 2024年3月22日下午9:17

思路：投票法：每个数开始时的票数votes=1，如果下一个数等于当前数，则votes++, 否则votes–.

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int maxium, votes=0;
        for (int &val: stock) {
            if (votes == 0) maxium = val;
            if (val == maxium) votes++;
            else votes--;
        }
        return maxium;
    }
};

0 赞同 0 条回复

heathhou 普通 2024年3月22日下午9:13

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        if(stock.size() <= 2){
            return stock[0];
        }

        int x = stock[0];
        int sum = 1;
        for(int i = 1; i < stock.size(); ++i){
            if(sum == 0){
                x = stock[i];
                sum = 1;
            }else{
                if(x == stock[i]){
                    sum++;
                }else{
                    sum--;
                }
            }
        }

    return x;
    }
};

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

0 赞同 0 条回复

王位詮釋普通 2024年3月22日下午9:09

看到这个题最开始想的就是直接使用哈希表来做：
class Solution {
    public int inventoryManagement(int[] stock) {
        if(stock.length==1){
            return stock[0];
        }
        Map<Integer,Integer> map = new HashMap<>();
        int result = 0;
        for(int i=0;i<stock.length;i++){
            if(map.containsKey(stock[i])){
                int temp = map.get(stock[i]);
                if(temp+1>stock.length/2){
                    result = stock[i];
                    break;
                }
                map.put(stock[i],temp+1);
            }else{
                map.put(stock[i],1);
            }
        }
        return result;
    }
}
之后觉得可以先进行排序，因为题中说了最多的数字是超过一半的，所以排序之后mid就是结果：
public int inventoryManagement(int[] stock) {//由于最多的数字超过一半，所以
        Arrays.sort(stock);
        int mid = stock.length/2;
        return stock[stock.length/2];
    }
然后是帅地最优解，摩尔投票法：
class Solution {
    public int inventoryManagement(int[] stock) {
        if(stock.length<=2){
            return stock[0];
        }
        int result = stock[0];
        int sum = 1;
        for(int i=1;i<stock.length;i++){
            if(sum==0){
                result = stock[i];
                sum = 1;
            }else{
                if(result==stock[i]){
                    sum++;
                }else{
                    sum--;
                }
            }
        }
        return result;   
    }
}

0 赞同 0 条回复

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

共以下 16 个回答

# 回答此问题取消回复

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

共以下 16 个回答

# 回答此问题 取消回复

# 回答此问题取消回复