Given an array of integers with duplicates, write a program to print unique elements in the array in sorted order.
This problem is also asked as Count Inversions in an array.
Java Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package javaapplication1; /** * * @author Lenovo */ import java.util.Arrays; import java.util.Iterator; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class JavaExample { public void countReversePairsDivideAndConquer(int [] input){ System.out.println("Input[] : " + Arrays.toString(input)); int totalInversions = divide(input, 0, input.length-1); System.out.println("Inversions count: " + totalInversions); } public int divide(int [] input, int low, int high){ if(low >= high) return 0; int mid = low + (high-low)/2; int leftInversions = divide(input, low, mid); int rightInversions = divide(input, mid+1, high); int mergeInversions = conquerAndCount(input, low, mid, high); return leftInversions + rightInversions + mergeInversions; } public int conquerAndCount(int [] input, int leftIndex, int midIndex, int rightIndex){ // temporary left sub array int[] left = Arrays.copyOfRange(input, leftIndex, midIndex + 1); // temporary right sub array int[] right = Arrays.copyOfRange(input, midIndex + 1, rightIndex + 1); int i = 0, j = 0, k = leftIndex, inversions = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) input[k++] = left[i++]; else { input[k++] = right[j++]; //count the inversions int count = (midIndex+1)-(leftIndex+i); inversions +=count; } } //fill rest of the elements from left array if any while(i<left.length) input[k++] = left[i++]; //fill rest of the elements from right array if any while(j<right.length) input[k++] = right[j++]; return inversions; } public static void main(String[] args){ int input[] = {10, 3, 4, 2, 5, 7, 9, 11}; JavaExample c = new JavaExample(); c.countReversePairsDivideAndConquer(input); } } |
Output:
