[LintCode] Majority Number I II III

sPeng 發布于2019-08-14 15:43 / 3462人閱讀

摘要：遍歷整個數組，用一個計數器，找出超過整個數組長度二分之一的那個數。規則是當前數等于，計數器加否則，計數器減。當的大小等于時，統計中所有的，并將所有對應的減，若被減為，就從中移除這對鍵值。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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