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

lQl 永久会员 2024年12月22日上午12:09

哈希:
时间复杂度O(n)
空间复杂度O(n)

class Solution {
    public int inventoryManagement(int[] stock) {
        int n = stock.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int s : stock) {
            if (map.containsKey(s)) {
                int now = map.get(s);
                map.put(s, now + 1);
            } else {
                map.put(s, 1);
            }
        }
        int id = 0;
        int max = 0;
        for (Integer key : map.keySet()) {
            if (map.get(key) > max) {
                max = map.get(key);
                id = key;
            }
        }
        return id;
    }
}

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

class Solution {
    public int inventoryManagement(int[] stock) {
        int n = stock.length;
        int id = 0;
        int num = 0;
        for (int s : stock) {
            if (num == 0)
                id = s;

            if (s == id)
                num++;
            else
                num--;
        }
        return id;
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月16日下午10:21

解题思路
– 假设第一个是众数，往后遍历，相同+1，不同-1，直到等于0；之后再找后续数组的第一个作为众数
– 因为众数的数量超过一半，所以剩下的一定是众数
【题解1】

class Solution {
    public int inventoryManagement(int[] stock) {
        // 假设第一个是众数，往后遍历，相同+1，不同-1，直到等于0；之后再找第一个作为众数
        // 因为众数的数量超过一半，所以剩下的一定是众数
        int target = stock[0];
        int count = 1;
        for (int i = 1; i < stock.length; i++) {
            int current = stock[i];
            // 判断count是否抵消为0了
            if (count == 0) {
                target = current;
            }
            // 判断假设的众数是否和当前值相等
            if (current == target) {
                count++;
            } else {
                count--;
            }
        }
        return target;

    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月16日上午11:38

class Solution {
    //思路：使用摩尔投票法
    public int inventoryManagement(int[] stock) {
        if(stock.length<=2) return stock[0];
        int num=1;
        int tmp=stock[0];
        for(int i=1;i<stock.length;i++){
            if(num==0){
                tmp=stock[i];
                num=1;
            }
            else{
                if(stock[i]==tmp) num++;
                else num--;
            }
        }
        return tmp;
    }
}
时间空间复杂度：o（N）

0 赞同 0 条回复

Aatorx 永久会员 2024年12月13日下午3:06

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int x = 0;
        int v = 0;
        for (int n : stock) {
            if (v == 0) {
                x = n;
            }
            if (n == x) {
                v++;
            }else {
                v--;
            }
        }
        return x;
    }
};

采用摩尔投票法，先假设众数为第一个元素，后面若出现相同的则加一，不同的则减一，做票数为0则重新选取当前元素众数。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

晓宇普通 2024年12月13日上午11:24

class Solution {    
    // 哈希表 
    int inventoryManagement(vector& stock) {
        unordered_map ids;
        int len = stock.size();
        for(int i = 0;i < len;i++){
            if(ids.find(stock[i]) == ids.end()) 
                ids.insert(pair(stock[i],1));
            else
                ids[stock[i]] += 1;
        }
        for(auto i = ids.begin();i != ids.end();i++){
            if(i->second > len / 2) return i->first;
        }
        return -1;

    } // on on
}

//摩尔投票法
class Solution {
public:
    // 寻找众数 
    int inventoryManagement(vector& stock) {
        int len = stock.size();
        if(len <= 2) return stock[0];
        int mass = stock[0];
        int sum = 1;

        for(int i = 1;i < len;i++){
            // 相异抵消；相同加一
            if(mass != stock[i]) sum -= 1;
            else sum += 1;
            // 更新众数
            if(sum == 0){
                mass = stock[i];
                sum  = 1;
            }
        }
        return mass;
    }
    // o(n) o(1)
};

0 赞同 0 条回复

月下足迹普通 2024年12月13日上午10:36

//Boyer-Moore 投票算法
class Solution {
public int inventoryManagement(int[] stock) {
int candidate = 0, count = 0;
for (int id : stock) {
if (count 0) {
candidate = id;
}
count += (id candidate) ? 1 : -1;
}

    return candidate;
}

}

0 赞同 0 条回复

Kisara 普通 2024年12月12日下午11:42

map方法

class Solution {
    public int inventoryManagement(int[] stock) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int n:stock){
            map.put(n,map.getOrDefault(n,0)+1);
        }

        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()>stock.length/2){
                return entry.getKey();
            }
        }
        return 0;
    }
}
```On On

摩尔投票法
```java
class Solution {
    public int inventoryManagement(int[] stock) {
       int result=0;
       int count=0;
       for(int n:stock){
        if(count==0) result=n;
        count+=n==result?1:-1;
       }

       return result;
    }
}

On O1

0 赞同 0 条回复

迢迢星野普通 2024年12月12日下午9:21

class Solution {
    /**
     * 仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。
     * 
     * 题意解读：摩尔投票法，给一个元素进行投票，如果是记录的众数，就 +1，否则 -1；当 votes 为 0 时，更换为最新元素
     * @param stock
     * @return
     */
    public int inventoryManagement(int[] stock) {
        int votes = 0, res = 0;
        for (int num : stock) {
            if (votes == 0) {
                res = num;
            }
            votes += num == res ? 1 : -1;
        }
        return res;
    }
}

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

0 赞同 0 条回复

jaron 普通 2024年12月12日下午9:07

神奇的方法

class Solution {
    public int inventoryManagement(int[] stock) {
        if (stock.length <= 2) {
            return stock[0];
        }
        int ans = stock[0];
        int cnt = 1;
        for (int i = 1; i < stock.length; i++) {
            if (cnt != 0) {
                if (stock[i] == ans) {
                    cnt++;
                } else {
                    cnt--;
                }
            } else {
                ans = stock[i];
                // 这里不要忘记++
                cnt++;
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复