數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
給一個長度為 n 的數(shù)組芙贫，數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字互亮。
例如輸入一個長度為9的數(shù)組[1,2,3,2,2,2,5,4,2]汗捡。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半走搁，因此輸出2。
- 兩件事迈窟。第一件事找眾數(shù)私植。第二件事檢查這個數(shù)有沒有超一半。
- 我從前往后查 i 個數(shù)车酣。這 i 個數(shù)中的那個眾數(shù)曲稼，他的數(shù)量一定大于其他數(shù)出現(xiàn)的次數(shù)『保可以認為
臨時眾數(shù) - 其他數(shù)出現(xiàn)次數(shù) > 0贫悄。 - 如果等于某次等于0了，說明有兩個候選的眾數(shù)了娘摔。此時不管窄坦，將新的那個數(shù)設(shè)為臨時眾數(shù)。因為按照題意凳寺，不管怎樣只會有一個眾數(shù)存在鸭津，如果存在兩個眾數(shù)，一定不會超過數(shù)組長度一半肠缨。那假設(shè)存在一個符合題意的眾數(shù)逆趋。在查到 i 的時候，兩個數(shù)出現(xiàn)的次數(shù)相同怜瞒，那么在后續(xù)的遍歷中父泳，肯定會因為次數(shù)的原因而改變?yōu)檎_答案般哼。
- 可以理解為查找眾數(shù)的一個算法吴汪。
- 眾數(shù)找出來了惠窄，遍歷一下就可以知道出現(xiàn)幾次了。
public int MoreThanHalfNum_Solution(int[] nums) {
int majority = nums[0];
for (int i = 1, cnt = 1; i < nums.length; i++) {
cnt = nums[i] == majority ? cnt + 1 : cnt - 1;
if (cnt == 0) {
majority = nums[i];
cnt = 1;
}
}
int cnt = 0;
for (int val : nums)
if (val == majority)
cnt++;
return cnt > nums.length / 2 ? majority : 0;
}
圓圈中最后剩下的數(shù)
讓小朋友們圍成一個大圈漾橙。然后杆融，隨機指定一個數(shù) m，讓編號為 0 的小朋友開始報數(shù)霜运。每次喊到 m-1 的那個小朋友要出列唱首歌脾歇，然后可以在禮品箱中任意的挑選禮物，并且不再回到圈中淘捡，從他的下一個小朋友開始藕各，繼續(xù) 0...m-1 報數(shù) .... 這樣下去 .... 直到剩下最后一個小朋友，可以不用表演焦除。
- 經(jīng)典約瑟夫環(huán)激况。
- 我們做題的時候，往往會不自覺的注重一道題的過程膘魄。比如這道題乌逐，我最開始的思路是哪些數(shù)死，死到最后创葡，哪個數(shù)活下來浙踢。但是，這道題的思路則要相反灿渴。直接想辦法確定哪個數(shù)活下來洛波，這個活下來的數(shù)，對后面的答案的影響骚露。
- 2個參數(shù)蹬挤。一個隨機數(shù)m，一個總?cè)藬?shù)n荸百∥帕妫看到兩個參數(shù)，首先想到的肯定是f(n,m)够话，先不管是什么函數(shù)蓝翰，用的什么方法，肯定存在這個函數(shù)女嘲。
- 那接下來就是找這個函數(shù)的對應(yīng)關(guān)系或者邏輯畜份。
-
針對這道題，我的理解是先畫圖欣尼，根據(jù)結(jié)果爆雹，反推邏輯停蕉。
紅色是第一個圈刪除 ， 綠色是第二個圈刪除钙态，黑色是第三個圈即以上刪除慧起。
a. m=2
m=2.png
b. m=3
m=3.png - 結(jié)論是上一個數(shù)的答案往后數(shù)m個，就是本次的答案册倒。
public int LastRemaining_Solution(int n, int m) {
if (n == 0) /* 特殊輸入的處理 */
return -1;
if (n == 1) /* 遞歸返回條件 */
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}
從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)
輸入一個整數(shù) n 蚓挤，求 1～n 這 n 個整數(shù)的十進制表示中 1 出現(xiàn)的次數(shù)
例如， 1~13 中包含 1 的數(shù)字有 1 驻子、 10 灿意、 11 、 12 崇呵、 13 因此共出現(xiàn) 6 次
注意：11 這種情況算兩次
- 先明確思路啊缤剧，按位計算1出現(xiàn)的次數(shù)，然后加起來域慷。
- 問題變成每一個位上1出現(xiàn)的次數(shù)荒辕，怎么計算。
- 123123芒粹，比如計算百位上1出現(xiàn)的次數(shù)時兄纺，開頭的123算往上計算，后面的23算向下計算化漆。
- 考慮2種情況估脆。
a. 這個位上的數(shù)字為1。
和123200百位上1出現(xiàn)的次數(shù)不同的是座云，最后一次循環(huán)疙赠，沒有123124-123199。
在往前的計算過程中朦拖，通過前3位123*100圃阳，即為1出現(xiàn)的次數(shù)。
在往后計算的過程中璧帝。通過最后兩位的可能性可知捍岳，有00-23的次數(shù)，為24次睬隶。即最后兩位+1锣夹。
b. 這個位上的數(shù)字為2-9。
和123200百位上1出現(xiàn)的次數(shù)類似苏潜，最后一次循環(huán)银萍，包含了123124-123199。
在往前的計算過程中恤左，前3位123+1贴唇，得到124搀绣，124*100即為1出現(xiàn)的次數(shù)。
沒有必要往后計算戳气。
c. 這個位上的數(shù)字位0链患。
假設(shè)為123023。
往前計算物咳，123*100锣险。
往后計算不了蹄皱。最后一次循環(huán)览闰，達不到1。 - 分類的計算方式巷折，代碼上看一眼就明白了压鉴。
+8確實很精彩。
public int NumberOf1Between1AndN_Solution(int n) {
int cnt = 0;
for (int m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
}
return cnt;
}
