[LintCode] Majority Number I II III

sPeng 发布于2019-08-14 15:43 / 3375人阅读

摘要：遍历整个数组，用一个计数器，找出超过整个数组长度二分之一的那个数。规则是当前数等于，计数器加否则，计数器减。当的大小等于时，统计中所有的，并将所有对应的减，若被减为，就从中移除这对键值。

Majority Number I Problem

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Note

遍历整个数组，用一个计数器count，找出超过整个数组长度二分之一的那个数res。规则是：当前数等于res，计数器加1；否则，计数器减1。若计数器为0，res更新为当前数num，计数器计1.

Solution

public class Solution {
    public int majorityNumber(ArrayList nums) {
        int res = nums.get(0), count = 0;
        for (int num: nums) {
            if (count == 0) {
                res = num;
                count = 1;
            }
            else if (num == res) count++;
            else count--;
        }
        return res;
    }
}

Majority Number II Problem

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.

Notice

There is only one majority number in the array.

Example

Given [1, 2, 1, 2, 1, 3, 3], return 1.

Challenge

O(n) time and O(1) extra space.

Note

和上一道题异曲同工，由于多于数组长度三分之一的数可能有两个，那么我们设置两个计数器，找出这两个数；再用两个计数器重新计数，找出个数更多的那个数，就是所求。

Solution

public class Solution {
    public int majorityNumber(ArrayList nums) {
        int size = nums.size();
        int a = 0, b = 0, ca = 0, cb = 0;
        for (int i = 0; i < size; i++) {
            if (nums.get(i) == a) ca++;
            else if (nums.get(i) == b) cb++;
            else if (ca == 0) {
                a = nums.get(i);
                ca++;
            }
            else if (cb == 0) {
                b = nums.get(i);
                cb++;
            }
            else {
                ca--;
                cb--;
            }
        }
        ca = cb = 0;
        for (int i = 0; i < size; i++) {
            if (nums.get(i) == a) ca++;
            else if (nums.get(i) == b) cb++;
        }
        return ca > cb ? a : b;
    }
}

Majority Number III Problem

Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

Find it.

Notice

There is only one majority number in the array.

Example

Given [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.

Challenge

O(n) time and O(k) extra space

Note

要求O(k)的space，即保证map的大小为k，但要通过所有的case，map的大小必须是k+1才满足，所以注意第8行的条件：
else if (map.size() < k+2) map.put(cur, 1);

其他的和上一道一样理解，建立一个HashMap，里面放入A中的不同的k+1个数，然后对这些数计数。当map的大小等于k+2时，统计map中所有的key，并将所有key对应的value减1，若value被减为0，就从map中移除这对键值。

这样，循环结束后，map中最多只剩下k个pair，找出其中value最大的key值，返回。

Solution

public class Solution {
    public int majorityNumber(ArrayList A, int k) {
        if (A.size() < k) return -1;
        Map map = new HashMap();
        for (int i = 0; i < A.size(); i++) {
            int cur = A.get(i);
            if (map.containsKey(cur)) map.put(cur, map.get(cur)+1);
            else if (map.size() < k+2) map.put(cur, 1);
            else {
                List keys = new ArrayList();
                for (Integer key: map.keySet()) keys.add(key);
                for (Integer key: keys) {
                    map.put(key, map.get(key)-1);
                    if (map.get(key) == 0) map.remove(key);
                }
            }
        }
        int res = 0, val = 0;
        for (Integer key: map.keySet()) {
            if (map.get(key) > val) {
                val = map.get(key);
                res = key;
            }
        }
        return res;
    }
}

私有云 GPU服务器 III II ii6 ii7

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65968.html

[LintCode] Backpack I II III IV V VI [背包六问]

摘要：单次选择最大体积动规经典题目，用数组表示书包空间为的时候能装的物品最大容量。注意的空间要给，因为我们要求的是第个值，否则会抛出。依然是以背包空间为限制条件，所不同的是取的是价值较大值，而非体积较大值。 Backpack I Problem 单次选择+最大体积 Given n items with size Ai, an integer m denotes the size of a b...

sutaking 2019-08-14 14:31 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
LintCode Coins in a line III

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LintCode/LeetCode] Single Number III

摘要：去掉最后一个保留最后一个保留最后一个保留第一个这道题在论坛里参考了和两位仁兄的解法。思想是将中所有的数进行异或运算。不同的两个数异或的结果，一定至少有一位为。最后，将和存入数组，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

lanffy 2019-08-14 15:33 评论0 收藏0