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