每日算法——letcode系列
問題 Remove Duplicates from Sorted Array II
Difficulty:<strong>Medium</strong></br>
<p><p>
Follow up for "Remove Duplicates":<br />
What if duplicates are allowed at most <i>twice</i>?</p>
<p>
For example,<br />
Given sorted array <i>nums</i> = <code>[1,1,1,2,2,3]</code>,</p>
<p>
Your function should return length = <code>5</code>, with the first five elements of <i>nums</i> being <code>1</code>, <code>1</code>, <code>2</code>, <code>2</code> and <code>3</code>. It doesn't matter what you leave beyond the new length.
</p></p>
// C++
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
}
};
翻譯 移除有序數(shù)組中重復(fù)元素II
難度系數(shù)：<strong>中等</strong></br>
接著上一個(gè)總是“刪除重復(fù)數(shù)”:<br />
如果可以重復(fù)的數(shù)最多只允許 <i>兩</i>次呢?</p>
例如,<br />
給定一個(gè)有序的數(shù)組 <i>nums</i> = <code>[1,1,1,2,2,3]</code>,
函數(shù)返回的長度應(yīng) = <code>5</code>,數(shù)組<i>nums</i>的前五個(gè)元素應(yīng)為 <code>1</code>, <code>1</code>, <code>2</code>, <code>2</code> 和<code>3</code>
思路
由于是有序的倦踢，上題是相鄰不能相等胃珍，現(xiàn)在相當(dāng)于是隔一個(gè)不能相等略吨，本質(zhì)上一樣, 可以和上一題寫一個(gè)通用的代碼
// C++
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = static_cast<int>(nums.size());
if (n < 3){
return n;
}
int index = 2;
for (int i = 2; i < n; ++i){
if (nums[index - 2] != nums[i]){
nums[index++] = nums[i];
}
}
for (int i = 0; i < n - index; ++i){
nums.pop_back();
}
return index;
}
};
// 通用
class Solution {
public:
/**
* remove duplicates if the number of duplicates more than num
*
* @param nums <#nums description#>
* @param num <#num description#>
*
* @return size of new nums
*/
int removeDuplicates(vector<int>& nums, int num) {
int n = static_cast<int>(nums.size());
if (n < num + 1){
return n;
}
int index = num;
for (int i = 2; i < n; ++i){
if (nums[index - num] != nums[i]){
nums[index++] = nums[i];
}
}
for (int i = 0; i < n - index; ++i){
nums.pop_back();
}
return index;
}
};
前文延伸解決
注：前文中文版?zhèn)€人覺得翻譯有問題宫患，不應(yīng)該是有序的笼踩，應(yīng)該是一系列整數(shù)， 有序的就太簡單了
分析
由于4 300 000 000大于$2{32}$，且1到$2{32}$中每個(gè)數(shù)都至少有一個(gè)，所以必須有重復(fù)的數(shù)添祸，題目設(shè)置成這么大的數(shù)，主要是不要考慮全部讀取到內(nèi)存的方案寻仗，為方便測試可以用1到256的取258個(gè)數(shù)（258 >$2^8$)來測試刃泌。
方案一：
用一個(gè)char類型的數(shù)據(jù)，由于一個(gè)char占8個(gè)字節(jié)署尤，每個(gè)字節(jié)兩個(gè)比特位耙替，一共有256個(gè)比特位，讀取一個(gè)數(shù)曹体，如果這個(gè)數(shù)是2俗扇，先判斷char類型數(shù)據(jù)的第二個(gè)比特位上是否為0，如果為0就把設(shè)置為1箕别，如果為1代表這個(gè)數(shù)出現(xiàn), 時(shí)間復(fù)雜度$T_{n} = O{(n)} $, 其實(shí)本質(zhì)上就是hashmap的方案铜幽，只不過更省空間滞谢。
方案二：
二分法（注：《編程珠璣》推薦的方案）
讀到一個(gè)數(shù)，最高比特位如果是0除抛，放在A堆爹凹，最高比特位如果是1放到B堆，這樣就把258镶殷，人為的分成了兩堆，現(xiàn)在如果哪堆的個(gè)數(shù)大于$256/2=128$, 證明重復(fù)的數(shù)在哪堆微酬，也有可能兩堆都有绘趋， 再讀最高位的下一位比特位再分堆，如此反復(fù)肯定能找到那個(gè)重復(fù)的數(shù)
延伸思考
如果是$2^{32}$ + 1個(gè)數(shù)呢颗管？也就是只有一個(gè)重復(fù)的數(shù)陷遮，怎么來找此數(shù)呢？有沒有更低的時(shí)間復(fù)雜度方案垦江？
