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

配列がすでにソートされている場合、重複する要素は必ず隣接しています。この性質を利用すると、2つのポインタ（i と j）を使った効率的なアルゴリズムで重複を削除できます。ここで i はゆっくり進む「スローポインタ」、j は速く進む「ファストポインタ」として機能します。

アルゴリズムの手順

nums[i] == nums[j] の間は重複が続いているため、j を1つずつ進めて重複をスキップしていきます。

nums[j] != nums[i] となった時点で、連続した重複が終わったことを意味します。そこで、その値を nums[i + 1] にコピーし、i をインクリメントしてから同じ処理を繰り返します。

j が配列の末尾に到達したら処理を終了します。最後に、重複が除去された要素を先頭から index 番目まで新しい配列にコピーし、その新しい配列を返します。

時間計算量：O(N)　※N は配列の要素数

C#での実装例

using System;
namespace ConsoleApplication{
    public class Arrays{
        public int[] RemoveDuplicatesFromSortedArrayAndReturnArray(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;
                }
            }
            int[] newarr = new int[index];
            for (int i = 0; i < index; i++){
                newarr[i] = arr[i];
            }
            return newarr;
        }
    }
    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.RemoveDuplicatesFromSortedArrayAndReturnArray(arr);
            for (int i = 0; i < res.Length; i++){
                Console.WriteLine(res[i]);
            }
            Console.ReadLine();
        }
    }
}

動作の流れ

入力配列 { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 } の場合、隣接する要素同士を比較しながら、異なる値だけを配列の前方へ順番に詰めていきます。ループが完了すると、先頭から index 番目までに重複のない要素が格納されているため、それを新しい配列として切り出して返します。

出力結果

0 1 2 3 4