อาร์เรย์ได้รับการจัดเรียงแล้ว เราสามารถเก็บพอยน์เตอร์สองตัว 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 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
