อาร์เรย์ได้รับการเรียงลำดับแล้ว เราสามารถใช้ two pointers ii และ jj โดย ii เป็น slow-runner ในขณะที่ jj เป็น fast-runnerตราบใดที่ nums[i] = nums[j] เราเพิ่ม jj เพื่อข้ามค่าซ้ำ
เมื่อเราพบ nums[j] != nums[i] ช่วงค่าซ้ำจบลง เราต้องคัดลอกค่าของมันไปที่ nums[i + 1] ii จึงถูกเพิ่มขึ้นและเราทำกระบวนการเดิมซ้ำจนกว่า jj จะถึงปลายอาร์เรย์ สร้างอาร์เรย์ใหม่ คัดลอกองค์ประกอบทั้งหมดจากอาร์เรย์ที่กรองแล้วจนถึงดัชนีและคืนค่าอาร์เรย์ใหม่
Time complexity - O(N)
ตัวอย่าง
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 1 2 3 4
