iT邦幫忙

DAY 16
1

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

[Day16] 30 天挑戰演算法 - 刪除指定元素

題目來源Remove element

問題
給予一個 int 陣列, 和一個指定的數字,請試著移除該陣列中的所有指定數字,並且回傳新的陣列大小。
並且請使用常數空間完成。(不要額外宣告一個陣列)

例子
例如:陣列 = [1 2 2 3 3 4 5 6 3 3 2 1], 指定數字 3
請將輸入陣列修改成 [1 2 2 4 5 6 2 1] 並回傳新的陣列大小為 8
(ps. 第8個以後元素是什麼都無所謂,因為扣掉所有指定數字後,只有八個數字,所以只看前八個)

想法
關於這種類型的題目,只要手動 trace 一遍很容易就可以找到他的邏輯了,不過重點是,我們需要兩個索引 i 和 index。index 存放的是沒有 指定數字 的位置,而 i 是在陣列中從頭跑到尾,如果遇到 指定數字就不理他,如果遇到 非指定數字,就把該數字 assign 給 index, 此時 index 就可以往下一格,等待 i 發現新的 非指定數字

以上面的例子為例:
一開始, i 和 index 都會指向 第一個 數字 1, 又因為第一個 數字 不是指定數字 所以,i 跟 index 都會同時往下跑,指向 第二個 數字 2 。

直到 i 跟 index 碰到了陣列裡的 第四個 數字 3 時,index 就會停住,直到 i 只到的數字 不是指定數字 3 ,並且將該數字給 index 替換掉,index 才會繼續往下。

此時,又因為 i 把那個位置的數字給 index 替換調了,所以 i 目前的數字就必須把他改成 指定數字 , 因為這樣一來就不會被 index 誤判。(非指定數字都會被留下來,這樣會影響到新的陣列大小)

所以根據以上的想法,我們的判斷式會有三種判斷:

  1. index 與 i 同時都沒遇到指定數字 -> 兩個都要往下走
  2. index 遇到指定數字 而 i 沒遇到, -> i 要把數字給 index 並且讓 index 往下走
  3. index 與 i 同時遇到指定數字 -> index 要停住,讓 i 繼續往下走

我的解法 c# 版本

public int removeElement(int[] data, int elem)
{
    int index = 0;
    for (int i = 0; i < data.Length; i++)
    {
            // index 與 i 都遇到 指定數字
        if (data[index] == elem && data[i] == elem)
        {
            // index 要停住,讓 i 往下走
        }
        // index 遇到, i 沒遇到
        else if (data[index] == elem && data[i] != elem)
        {
            data[index] = data[i];
            index++;
            data[i] = elem;
        }
        // index 與 i 都沒遇到
        else if (data[index] != elem && data[i] != elem)
        {
            index++;
        }
    }
    return index;
}

根據上面的程式,我們可以發現 i 是跟著 for 迴圈跑,所以在第一種情況下 (index 與 i 都遇到指定數字) 只有 i 往下走,所以可以把那個判斷式拿掉 (因為不用作任何事情),不過記得拿掉之後還是要跑一下 test case , 以確保我們的想法沒錯。然後在 extract method 兩個判斷式,程式碼就會更清晰了。

After Refactor

public int removeElement(int[] data, int elem)
{
    int index = 0;
    for (int i = 0; i < data.Length; i++)
    {
        if (data[index] == elem && data[i] != elem)                
        {
            data[index] = data[i];
            index++;
            data[i] = elem;
        }
        else if (data[index] != elem && data[i] != elem)
        {
            index++;
        }
    }
    return index;
}

上一篇
[Day15] 30 天挑戰演算法 - 相同的樹
下一篇
[Day17] 30 天挑戰演算法 - 萬用字元配對
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言