iT邦幫忙

DAY 14
1

連續30天,挑戰演算法系列 第 14

[Day14] 30 天挑戰演算法 - 從排序陣列中刪除重複值

題目來源Remove duplicates from sorted array

問題:
給予一個已排序過的陣列(ARRAY),請計算移 除該陣列中所有重複出現過的數值(每個數字只能出現過一次)後的陣列長度。
限制:不要使用宣告其他的陣列方式來完成這個題目,也就是說你必須使用常數空間(constant memory) 來完成。

例子:
題目給予一個陣列 A = [1, 1, 2, 2, 3, 4, 5, 5, 7]
你的 方法 必須回傳新的長度為 6, 並且 A 必須是 [1, 2, 3, 4, 5, 7 ]

想法
這個題目最直覺得方是就是將只出現過一次的數值存到另一個陣列上,接著再 回傳該陣列的長度 並 將新的陣列複製到題目給予的陣列上 就完成了,非常的簡單。但是這樣做的缺點就是會浪費 N 個記憶體空間(,所以題目擺明了說,必須使用常數空間來完成,所以我們必須想另一個方法來完成這個題目。因此,首先我們先要列出題目給我們什麼和我們要回傳什麼:

題目給我們的是:

  1. 一個長度為N並且排序過的陣列

我們要回傳的是:

  1. 將傳進來的陣列裡重複的值刪除,並且將後面非重複值遞補上
  2. 新的陣列長度

並且題目有限制不能宣告其他的陣列空間,所以我們只能利用題目給的陣列空間來完成要求。所以我們會需要一個 index 來幫助我們記住新的陣列長度。

舉例來說,題目給一個陣列
Data = [1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5]
則當我們處理完後,這個陣列 Data 應該是會長的像這樣
Data = [1, 2, 3, 4, 5, 3, 4, 4, 4, 4, 5]
此時我們的 index 應該指向 5 告訴我們新的陣列尾端。如此一來就可以達到不用宣告新的陣列空間完成題目的要求了。

所以我的作法是,兩個指標 index 和 i , i 是原本陣列的指標,index 則是刪除重複值後的指標,所以當 data[index] 與 data[i] 的值相等時,i 會往前跑而 index 會停留在原本的地方直到找到 data[index] 不等於 data[i] 為止。
當 Data[i] 與 Data[index] 的值不同時,index 就會往後跑一格,並且將 data[i] 的值設給 data[index]。
我們用一個範例來說明:

輸入 data[] = [1, 1, 1, 2, 3, 3, 3, 4]

  1. 首先 index=0, i=0 => data[i] 與 data[index] 相等, 所以 i往下一格(i=1)

  2. index=0, i=1 => data[i] 與 data[index] 相等, i往下一格(i=2)

  3. ndex=0, i=2 => data[i] 與 data[index] 相等, i往下一格(i=3)

  4. index=0, i=3 => data[i] 與 data[index] 不相等, index往下一格, data[i] 設給 data[index], i往下一格(i=4)
    得到 [1, **2**, 1, 2, 3, 3, 3, 4 ]

  5. index=1, i=4 =>data[i] 與 data[index] 不相等, index往下一格, data[i] 設給 data[index, i 往下一格(i=5)
    得到 [1, 2, **3**, 2, 3, 3, 3, 4 ]

  6. index=2, i=5, => data[i] 與 data[index] 相等, i往下一格(i=6)

  7. index=2, i=6, => data[i] 與 data[index] 相等, i往下一格(i=7)

  8. index=2, i=7, => data[i] 與 data[index] 不相等, index往下一格, data[i] 設給 data[index], i 到底了
    得到 [1, 2, 3, **4**, 3, 3, 3, 4]

此時的 index 為 3 (指向第一個 4 的位置), 因為我們的 array 是從0開始,所以要回傳 index + 1
因此要回傳處理過的陣列大小為 4

簡單來說, index 所負責的功能就是,只有與我不同的值才能夠放到我的下一個位置。看一下程式碼吧,你會更清楚!

// java 我的解法 java 版本
public int removeDuplicates(int[] data) {
    if (data.length == 0)
        return 0;
    
    int index = 0;
    for (int i = 0; i < data.length; i++) {
        if (data[index] != data[i]) { // 與我不同的值
            index++; // 下一個位置
            data[index] = data[i]; // 放進來
        }
    }
    return index + 1;
}






# python 我的解法 python 版本
def removeDuplicates(self, A):
  if len(A) == 0 :
    return 0
  index = 0
  for i in range(0, len(A), 1):
    if A[i] != A[index]:
      index += 1
      A[index] = A[i]
  return index + 1

上一篇
[Day13] 30 天挑戰演算法 - 二元樹的最大深度
下一篇
[Day15] 30 天挑戰演算法 - 相同的樹
系列文
連續30天,挑戰演算法30

2 則留言

0
lulubear
iT邦新手 5 級 ‧ 2014-10-14 09:59:25

認真好文 ^^

我要留言

立即登入留言