C#でソート済み配列から重複を削除し、新しい長さを返す方法

アルゴリズムの考え方：ツーポインタ（二つのポインタ）を使う

配列がすでにソートされている場合、ツーポインタ手法が非常に有効です。2つのインデックス i と j を用意し、i を「遅いランナー（スローランナー）」、j を「速いランナー（ファストランナー）」として扱います。

nums[i] と nums[j] が等しい間は、j を進めることで重複要素をスキップしていきます。

nums[j] != nums[i] となった時点で、重複の連続が終わったことを意味します。このとき、その値を nums[i + 1] にコピーし、i をインクリメントします。あとは j が配列の末尾に到達するまで、同じ処理を繰り返すだけです。

時間計算量： O(N)

C#での実装例

using System;
namespace ConsoleApplication{
    public class Arrays{
        public int RemoveDuplicatesFromSortedArrayAndReturnLength(int[] arr){
            int index = 1;
            for (int i = 0; i < arr.Length - 1; i++){
                if (arr[i] != arr[i + 1]){
                    arr[index] = arr[i + 1];
                    index++;
                }
                else{
                    continue;
                }
            }
            return index;
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
            int res = a.RemoveDuplicatesFromSortedArrayAndReturnLength(arr);
            Console.WriteLine(res);
            Console.ReadLine();
        }
    }
}

出力結果

5

この例では、入力配列 { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 } に含まれる一意な要素は 0, 1, 2, 3, 4 の5つであるため、メソッドは 5 を返します。重複を除いた要素は配列の先頭側に順に詰められます。