Remove duplicates from sorted array

Remove duplicates from sorted array

Given a sorted array, the task is to remove the duplicate elements from the array.


Examples:

1)

Input  : arr[] = {2, 2, 2, 2, 2}

Output : arr[] = {2}

         new size = 1

2)

Input  : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}

Output : arr[] = {1, 2, 3, 4, 5}

         new size = 5

Method 1: (Using extra space)


Create an auxiliary array temp[] to store unique elements.

Traverse input array and one by one copy unique elements of arr[] to temp[]. Also keep track of count of unique elements. Let this count be j.

Copy j elements from temp[] to arr[] and return j

// simple java program to remove 

// duplicates 


Solution:


class Main 

{ 

// Function to remove duplicate elements 

// This function returns new size of modified 

// array. 

static int removeDuplicates(int arr[], int n) 

{ 

// Return, if array is empty 

// or contains a single element 

if (n==0 || n==1) 

return n; 

int[] temp = new int[n]; 

// Start traversing elements 

int j = 0; 

for (int i=0; i<n-1; i++) 

// If current element is not equal 

// to next element then store that 

// current element 

if (arr[i] != arr[i+1]) 

temp[j++] = arr[i]; 

// Store the last element as whether 

// it is unique or repeated, it hasn't 

// stored previously 

temp[j++] = arr[n-1]; 

// Modify original array 

for (int i=0; i<j; i++) 

arr[i] = temp[i]; 

return j; 

} 

public static void main (String[] args) 

{ 

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

int n = arr.length; 

n = removeDuplicates(arr, n); 

// Print updated array 

for (int i=0; i<n; i++) 

System.out.print(arr[i]+" "); 

} 

} 


Reference: Remove duplicates from sorted array


                                                                   Happy Coding💻:-)


Comments

Post a Comment

Popular posts from this blog

Valid Username Regular Expression

Valid Username Regular Expression: Problem Description: You are updating the username policy on your company's internal networking platform. According to the policy, a username is considered valid if all the following constraints are satisfied: The username consists of 8 to 30 characters inclusive. If the username consists of less than  or greater than 8 characters, then it is an invalid username. The username can only contain alphanumeric characters and underscores (_). Alphanumeric characters describe the character set consisting of lowercase characters[a-z] , uppercase characters[A-Z] , and digits[0-9]. The first character of the username must be an alphabetic character, i.e., either lowercase character [a-z] or uppercase character [A-Z]. Update the value of regularExpression field in the UsernameValidator class so that the regular expression only matches with valid usernames. Input Format The first line of input contains an integer , describing the total number of usernames. Ea...
Read more

Rotate String in Right Direction in java

Rotate String in Right Direction in java: Program: import java.util.*; public class RotateString { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); char[] ch = new char[n]; for(int i=0;i<n;i++) { ch[i] = s.next().charAt(0); } int r = s.nextInt(); char temp = 'a'; r=r%n; while(r>0) { temp = ch[n-1]; for(int i = n-1; i>0;i--) { ch[i] = ch[i-1]; } ch[0] = temp; System.out.println("r: " + r); for(int i=0;i<n;i++) { System.out.print(ch[i]); } System.out.println(); r--; } for(int i=0;i<n;i++) { System.out.print(ch[i]); } } } Output : 5 a s d f g 3 r: 3 gasdf r: 2 fgasd r: 1 dfgas dfgas                                                            Happy Coding 💻:-)
Read more

Java MCQ's

1) Predict the output of following Java Programs. Program 1: // filename Main.java  class Test {      protected int x, y;  }  class Main {      public static void main(String args[]) {          Test t = new Test();          System.out.println(t.x + " " + t.y);      }  }  Output:  0 0 Explanation: In Java, a protected member is accessible in all classes of same package and in inherited classes of other packages. Since Test and Main are in same package, no access related problem in the above program. Also, the default constructors initialize integral variables as 0 in Java (See this GFact for more details). That is why we get output as 0 0. Program 2: // filename Test.java  class Test {      public static void main(String[] args) {          for(int i = 0; 1; i++) {              System.ou...
Read more