อาร์เรย์ได้รับการจัดเรียงแล้ว เราสามารถเก็บพอยน์เตอร์สองตัว ii และ jj โดยที่ ii เป็นตัววิ่งช้าในขณะที่ jj เป็นตัวเร่งความเร็ว ตราบใดที่ nums[i] =nums[j]nums[i]=nums[j] เราเพิ่ม jj เพื่อข้ามรายการที่ซ้ำกัน
เมื่อเราพบ nums[j] !=nums[i] การรันซ้ำได้สิ้นสุดลง ดังนั้นเราต้องคัดลอกค่าของมันไปที่ nums[i + 1]nums[i+1] ii จะเพิ่มขึ้นและเราทำซ้ำขั้นตอนเดิมอีกครั้งจนกระทั่ง jj ถึงจุดสิ้นสุดของอาร์เรย์ สร้างอาร์เรย์ใหม่ คัดลอกองค์ประกอบทั้งหมดจากอาร์เรย์ที่กรองจนถึงดัชนีและส่งคืนอาร์เรย์ใหม่
ความซับซ้อนของเวลา − 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
