資訊專欄INFORMATION COLUMN
摘要：原文地址題目給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。示例給定函數(shù)應(yīng)該返回新的長(zhǎng)度并且原數(shù)組的前五個(gè)元素被修改為。
原文地址: https://www.luoyangfu.com/art...題目
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
示例 1:
給定數(shù)組 nums = [1,1,2], 函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2。 你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
示例 2:
給定 nums = [0,0,1,1,1,2,2,3,3,4], 函數(shù)應(yīng)該返回新的長(zhǎng)度 5, 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
說明:
為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請(qǐng)注意，輸入數(shù)組是以“引用”方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的。也就是說，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長(zhǎng)度, 它會(huì)打印出數(shù)組中該長(zhǎng)度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路
根據(jù)題目說明:
排序的數(shù)組 -> 數(shù)組是有序的
原地刪除重復(fù)數(shù)組 -> 不能移除
每個(gè)元素只出現(xiàn)一次 -> 時(shí)間復(fù)雜度O(n)
不能使用額外的數(shù)組空間 -> 不能復(fù)制元素
不用考慮數(shù)組中超出長(zhǎng)度的數(shù)據(jù) -> 和第2條對(duì)應(yīng)，把要移除的元素放到后面
我們需要在 時(shí)間復(fù)雜度為O(n) 情況下為一個(gè)有序的數(shù)組做一個(gè)刪除， 我們使用一個(gè)計(jì)數(shù)變量 i = 0 來標(biāo)記當(dāng)前數(shù)組不重復(fù)的數(shù)據(jù)的，但是這個(gè)時(shí)候我們需要 原地刪除 數(shù)組，這個(gè)時(shí)候就需要重復(fù)的數(shù)據(jù)放到后面，這樣返回的數(shù)據(jù)就可以保持在前面 i 個(gè)數(shù)據(jù)是不重復(fù)的。既然需要和后面元素交換，數(shù)組交換需要兩個(gè)下表，我們這里再采用另外一個(gè) 計(jì)數(shù)變量j 來表示作為當(dāng)前數(shù)組遍歷計(jì)數(shù)變量. 根據(jù)上述描述，我們使用的方法也稱之為雙指針法. 這里i 稱之為慢指針， j 稱之為快指針
雙指針，顧名思義，就是利用兩個(gè)指針去遍歷數(shù)組，一般來說，遍歷數(shù)組采用的是單指針（index）去遍歷，兩個(gè)指針一般是在有序數(shù)組中使用，一個(gè)放首，一個(gè)放尾，同時(shí)向中間遍歷，直到兩個(gè)指針相交，完成遍歷，時(shí)間復(fù)雜度也是O(n)。解決方法
根據(jù)解決思路我們這里使用 javascript 語(yǔ)法來開發(fā):
function removeDuplicates(arr) {
if(!Array.isArray(nums) || !nums.length) return 0;
if(nums.length < 2) return 1;
var i = 0;
for(var j = 1; j < nums.length; j ++) {
if(nums[i] !== nums[j]) {
i ++;
nums[i] = nums[j]
}
}
return ++i;
}
上面代碼有兩點(diǎn)要解釋的，判斷 nums[i] !== nums[j] 這里，當(dāng)他們不相等的時(shí)候進(jìn)行 i 和 j 的位置交換, 當(dāng)相同的時(shí)候j 就跳過相同的元素的， i++ 就在不同的下一個(gè)元素進(jìn)行交換。 在最后返回 ++i 這里，以為 i 是從0開始，因此長(zhǎng)度需要+1.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/104625.html
摘要：題目解析題目含義很簡(jiǎn)單，即求出沒有字符重復(fù)的子字符串的長(zhǎng)度。例如很明顯就是個(gè)由完全重復(fù)字符組成的字符串，所以它的答案長(zhǎng)度為。所以綜合來看該算法的效率為。 題目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...
摘要：我們需要找出中的數(shù)字的不同組合，使得每一種組合的元素加和為。輸入的候選集和目標(biāo)數(shù)字結(jié)果集是想法這道題采取了遞歸的思路。每次將一個(gè)元素加入的時(shí)候，判斷是否滿足中的元素加和等于，如果等于，直接將加入最終返回的結(jié)果集。 題目詳情 Given a set of candidate numbers (C) (without duplicates) and a target number (T),...
摘要：快慢指針法復(fù)雜度時(shí)間空間思路這是一道非常經(jīng)典的雙指針題。如果快指針和慢指針相遇，則說明鏈表有環(huán)。代碼快慢指針法復(fù)雜度時(shí)間空間思路這題是基于上一題，上一題我們發(fā)現(xiàn)相遇后就返回了，而這里我們還要繼續(xù)找到環(huán)的起始點(diǎn)。 Linked List Cycle I Given a linked list, determine if it has a cycle in it.Follow up: Ca...
摘要：描述給定一個(gè)有序數(shù)組，你需要原地刪除其中的重復(fù)內(nèi)容，使每個(gè)元素只出現(xiàn)一次并返回新的長(zhǎng)度。最后慢指針指向的元素及前面所有元素都是不重復(fù)的。 描述： 給定一個(gè)有序數(shù)組，你需要原地刪除其中的重復(fù)內(nèi)容，使每個(gè)元素只出現(xiàn)一次,并返回新的長(zhǎng)度。不要另外定義一個(gè)數(shù)組，您必須通過用 O(1) 額外內(nèi)存原地修改輸入的數(shù)組來做到這一點(diǎn)。示例： 給定數(shù)組: nums = [1,1,2], 你的函數(shù)應(yīng)該返回新...
摘要：題目描述給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。示例給定函數(shù)應(yīng)該返回新的長(zhǎng)度并且原數(shù)組的前五個(gè)元素被修改為。也就是說，不對(duì)實(shí)參做任何拷貝在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的。 題目描述 給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。 不要使用額外的數(shù)組空間，你必須在原地修改輸...
閱讀 2248·2021-11-18 10:02
閱讀 3499·2021-11-15 11:36
閱讀 1124·2019-08-30 14:03
閱讀 741·2019-08-30 11:08
閱讀 2772·2019-08-29 13:20
閱讀 3295·2019-08-29 12:34
閱讀 1382·2019-08-28 18:30
閱讀 1648·2019-08-26 13:34
