Saturday, 13 April 2019

Algorithms | Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length.

Example 1:
Given array = [1,1,2],

The function should return length=2, with the first two elements of array being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:
Given array= [0,0,1,1,1,2,2,3,3,4],

The function should return length=5, with the first five elements of array being modified to 0,1,2,3 and 4 respectively.

Note:
The auxiliary space should not be used and the return the index will fetch the element from start to return index for tests.

public class RemoveDuplication {

        /**
         * This method removes duplicates and return the index till non-duplicate
         * element are exits.
         *
         * @param nums
         * @return
         */
        public static int removeDuplicates(int[] nums) {
            if (nums == null) {
                return 0;
            } else if (nums.length == 0 || nums.length == 1) {
                return nums.length;
            }

            int i = 0;
            int j = 1;
            int len = nums.length;

            while (i < len && j < len) {
                if (nums[i] == nums[j]) {
                    j++;
                } else {
                    nums[++i] = nums[j++];
                }
            }

            return i + 1;
        }

        /**
         * Test method to remove duplicates.
         *
         */
        private static void testRemoveDuplicates() {

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

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

            int eIdx = removeDuplicates(array);

            if (Arrays.equals(resultArray, Arrays.copyOfRange(array, 0, eIdx))) {
                System.out.println("Tests are passed");
            } else {
                System.err.println("Tests are failed");
            }
        }
        /**
         * Driver method.
         *
         * @param args
         */
        public static void main(String[] args) {
            testRemoveDuplicates();
        }
    }


No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...