Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array

एक sorted array को देखते हुए, duplicate को हटा दें जैसे कि each element केवल एक बार दिखाई देता है और new length return करता है। another array के लिए extra space allocate न करें, आपको इसे Constant memory के साथ करना होगा।
उदाहरण के लिए, दिए गए Input Array A = [1,1,2], आपके function की length = 2 return करनी चाहिए, और A अब [1,2] है।

⦁ Thoughts
Problem काफी Simple है। यह unique elements के साथ array की length return करता है, लेकिन original array को भी बदलने की आवश्यकता है। इस issue की समीक्षा सॉर्ट किए गए Array II से duplicate निकालें के साथ की जानी चाहिए।

⦁ Solution 1

// Manipulate original array


public static int removeDuplicatesNaive(int[] A) {

if (A.length < 2)
return A.length;

int j = 0; int i = 1;

while (i < A.length) {

if (A[i] == A[j]) {
i++;
}

else { j++;
A[j] = A[i]; i++;
}
}

return j + 1;
}


This method returns the number of unique elements, but does not change the orig- inal array correctly. For example, if the input array is 1, 2, 2, 3, 3, the array will be changed to 1, 2, 3, 3, 3. The correct result should be 1, 2, 3. Because array’s size can not be changed once created, there is no way we can return the original array with correct results.

⦁ Solution 2

public static int[] removeDuplicates(int[] A) {
if (A.length < 2)

return A;

int j = 0; int i = 1;

while (i < A.length) {

if (A[i] == A[j]) {
i++;
}

else {

j++;
A[j] = A[i]; i++;
}
}

int[] B = Arrays.copyOf(A, j + 1);

return B;
}

public static void main(String[] args) {

int[] arr = { 1, 2, 2, 3, 3 };
arr = removeDuplicates(arr);

System.out.println(arr.length);
}


In this method, a new array is created and returned.

⦁ Solution 3

यदि हम only unique elements की संख्या count करना चाहते हैं, तो following methods good है।
// Count the number of unique elements


public static int countUnique(int[] A) {
int count = 0;
for (int i = 0; i < A.length – 1; i++) {

if (A[i] == A[i + 1]) {
count++;
}
}
return (A.length – count);
}

public static void main(String[] args) {

int[] arr = { 1, 2, 2, 3, 3 };

int size = countUnique(arr);

System.out.println(size);
}

LEAVE A REPLY

Please enter your comment!
Please enter your name here