Write a noDups() method for the HighArray class of the highArray.java program. T

ID: 3885544 • Letter: W

Question

Write a noDups() method for the HighArray class of the highArray.java program. This method should remove all duplicates from the array. That is , if three items with the key 17 appear in the array, noDups() should remove two of the. Don't worry about maintaining the order of the items. One approach is to first compare every item with all the other items and overwrite any duplicates with a null (or distinctive value that isn't used for real keys). Then remove all the nulls. Of course, the array size will be reduced.

Explanation / Answer

We have created a function called noDups() that works on sorted array ( even is array is unsorted we can sort it using in-built Arrays.sort() ) and this function returns the modified/new size of the array after removing the dupiicate values. So to get/work on new array we have to consider the original array till index n returned from the function.

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

{

//Sort the array

Arrays.sort(arr);

// 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;

}

Approach:

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

2.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.

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

Sample Test Case:

public static void main (String[] args)

{

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

int n = arr.length;

//The function return the new/modiied size/length of array with no duplicates.

n = removeDuplicates(arr, n);

// Print updated array ( we only need to traverse till modified size/leng

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

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

}

Output:

1 2 3 4 5