資訊專欄INFORMATION COLUMN
摘要：雙指針?lè)◤?fù)雜度時(shí)間空間思路我們可以將不重復(fù)的序列存到數(shù)列前面，因?yàn)椴恢貜?fù)序列的長(zhǎng)度一定小于等于總序列，所以不用擔(dān)心覆蓋的問(wèn)題。代碼雙指針?lè)◤?fù)雜度時(shí)間空間思路思路和上題一樣，區(qū)別在于記錄前兩個(gè)遍歷到的數(shù)字來(lái)幫助我們判斷是否出現(xiàn)了第三遍。
Remove Duplicates from Sorted Array I
雙指針?lè)?/b> 復(fù)雜度Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn"t matter what you leave beyond the new length.
時(shí)間 O(N) 空間 O(1)
思路我們可以將不重復(fù)的序列存到數(shù)列前面，因?yàn)椴恢貜?fù)序列的長(zhǎng)度一定小于等于總序列，所以不用擔(dān)心覆蓋的問(wèn)題。具體來(lái)說(shuō)，用兩個(gè)指針，快指針指向當(dāng)前數(shù)組遍歷到的位置，慢指針指向不重復(fù)序列下一個(gè)存放的位置，這樣我們一旦遍歷到一個(gè)不重復(fù)的元素，就把它復(fù)制到不重復(fù)序列的末尾。判斷重復(fù)的方法是記錄上一個(gè)遍歷到的數(shù)字，看是否一樣。
代碼public class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0) return 0;
int dup = nums[0];
int end = 1;
for(int i = 1; i < nums.length; i++){
if(nums[i]!=dup){
nums[end] = nums[i];
dup = nums[i];
end++;
}
}
return end;
}
}
Remove Duplicates from Sorted Array II
雙指針?lè)?/b> 復(fù)雜度Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn"t matter what you leave beyond the new length.
時(shí)間 O(N) 空間 O(1)
思路思路和上題一樣，區(qū)別在于記錄前兩個(gè)遍歷到的數(shù)字來(lái)幫助我們判斷是否出現(xiàn)了第三遍。如果當(dāng)前數(shù)字和前一個(gè)數(shù)字的前一個(gè)一樣的話，說(shuō)明出現(xiàn)了第三次。
代碼public class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length <= 2) return nums.length;
int dup1 = nums[0];
int dup2 = nums[1];
int end = 2;
for(int i = 2; i < nums.length; i++){
if(nums[i]!=dup1){
nums[end] = nums[i];
dup1 = dup2;
dup2 = nums[i];
end++;
}
}
return end;
}
}
Follow Up 后續(xù)
Q：如果數(shù)組沒(méi)有排序的話如何解？
A：可以先將其排序再用同樣方法求解，然而時(shí)間復(fù)雜度將達(dá)到O(NlogN)，如果我們改用哈希表或集合來(lái)記錄數(shù)字出現(xiàn)次數(shù)，可以用O(N)空間得到O(N)的時(shí)間。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64521.html
摘要：思路原數(shù)組長(zhǎng)度為，則返回原數(shù)組長(zhǎng)度不為，則至少有個(gè)元素。將所有不重復(fù)的數(shù)值賦給，而當(dāng)和相等時(shí)，不做處理。最后返回的就是不同元素的個(gè)數(shù)，也是新數(shù)組的長(zhǎng)度。只有在時(shí)，才對(duì)賦值。注意，每次初始化的時(shí)候要分兩種情況，這就意味著從的時(shí)候開(kāi)始遍歷。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...
摘要：思路與代碼其實(shí)在這里我們?nèi)匀谎永m(xù)中的思路。在遇到非重復(fù)值以及非多余的重復(fù)值時(shí)，將數(shù)值移動(dòng)到當(dāng)前記錄的下標(biāo)上。保證該下標(biāo)前的值均為滿足題目條件的值。第一次我使用了來(lái)記錄某個(gè)值出現(xiàn)的次數(shù)。 題目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...
摘要：題目比較簡(jiǎn)單，就是找出數(shù)組不重復(fù)的數(shù)字，返回不重復(fù)的數(shù)字個(gè)數(shù)。無(wú)需刪除重復(fù)數(shù)字，只需要保證數(shù)組的前位為不重復(fù)的個(gè)數(shù)字即可代碼如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...
閱讀 2780·2023-04-25 20:19
閱讀 2031·2021-11-24 09:38
閱讀 1795·2021-11-16 11:44
閱讀 4976·2021-09-02 15:40
閱讀 1480·2019-08-30 15:55
閱讀 2099·2019-08-30 15:52
閱讀 3879·2019-08-29 17:20
閱讀 2449·2019-08-29 13:48
