資訊專欄INFORMATION COLUMN
摘要：遍歷整個(gè)數(shù)組，用一個(gè)計(jì)數(shù)器，找出超過(guò)整個(gè)數(shù)組長(zhǎng)度二分之一的那個(gè)數(shù)。規(guī)則是當(dāng)前數(shù)等于，計(jì)數(shù)器加否則，計(jì)數(shù)器減。當(dāng)?shù)拇笮〉扔跁r(shí)，統(tǒng)計(jì)中所有的，并將所有對(duì)應(yīng)的減，若被減為，就從中移除這對(duì)鍵值。
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.
ExampleGiven [1, 1, 1, 1, 2, 2, 2], return 1
ChallengeO(n) time and O(1) extra space
Note遍歷整個(gè)數(shù)組，用一個(gè)計(jì)數(shù)器count，找出超過(guò)整個(gè)數(shù)組長(zhǎng)度二分之一的那個(gè)數(shù)res。規(guī)則是：當(dāng)前數(shù)等于res，計(jì)數(shù)器加1；否則，計(jì)數(shù)器減1。若計(jì)數(shù)器為0，res更新為當(dāng)前數(shù)num，計(jì)數(shù)器計(jì)1.
Solutionpublic 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.
NoticeThere is only one majority number in the array.
ExampleGiven [1, 2, 1, 2, 1, 3, 3], return 1.
ChallengeO(n) time and O(1) extra space.
Note和上一道題異曲同工，由于多于數(shù)組長(zhǎng)度三分之一的數(shù)可能有兩個(gè)，那么我們?cè)O(shè)置兩個(gè)計(jì)數(shù)器，找出這兩個(gè)數(shù)；再用兩個(gè)計(jì)數(shù)器重新計(jì)數(shù)，找出個(gè)數(shù)更多的那個(gè)數(shù)，就是所求。
Solutionpublic 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.
NoticeThere is only one majority number in the array.
ExampleGiven [3,1,2,3,2,3,3,4,4,4] and k=3, return 3.
ChallengeO(n) time and O(k) extra space
Note要求O(k)的space，即保證map的大小為k，但要通過(guò)所有的case，map的大小必須是k+1才滿足，所以注意第8行的條件：
else if (map.size() < k+2) map.put(cur, 1);
其他的和上一道一樣理解，建立一個(gè)HashMap，里面放入A中的不同的k+1個(gè)數(shù)，然后對(duì)這些數(shù)計(jì)數(shù)。當(dāng)map的大小等于k+2時(shí)，統(tǒng)計(jì)map中所有的key，并將所有key對(duì)應(yīng)的value減1，若value被減為0，就從map中移除這對(duì)鍵值。
這樣，循環(huán)結(jié)束后，map中最多只剩下k個(gè)pair，找出其中value最大的key值，返回。
Solutionpublic 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65968.html
摘要：?jiǎn)未芜x擇最大體積動(dòng)規(guī)經(jīng)典題目，用數(shù)組表示書(shū)包空間為的時(shí)候能裝的物品最大容量。注意的空間要給，因?yàn)槲覀円蟮氖堑趥€(gè)值，否則會(huì)拋出。依然是以背包空間為限制條件，所不同的是取的是價(jià)值較大值，而非體積較大值。 Backpack I Problem 單次選擇+最大體積 Given n items with size Ai, an integer m denotes the size of a b...
摘要：和唯一的不同是組合中不能存在重復(fù)的元素，因此，在遞歸時(shí)將初始位即可。 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...
摘要：復(fù)雜度思路參考的思路，對(duì)于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價(jià)值。對(duì)于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個(gè)的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個(gè)值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：去掉最后一個(gè)保留最后一個(gè)保留最后一個(gè)保留第一個(gè)這道題在論壇里參考了和兩位仁兄的解法。思想是將中所有的數(shù)進(jìn)行異或運(yùn)算。不同的兩個(gè)數(shù)異或的結(jié)果，一定至少有一位為。最后，將和存入數(shù)組，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...
閱讀 2669·2021-11-23 09:51
閱讀 2427·2021-09-30 09:48
閱讀 2057·2021-09-22 15:24
閱讀 1020·2021-09-06 15:02
閱讀 3320·2021-08-17 10:14
閱讀 1951·2021-07-30 18:50
閱讀 1990·2019-08-30 15:53
閱讀 3189·2019-08-29 18:43
