Java + Count duplicates from int array without usi

Question

As a part of the Java interview question paper I have got following issue to solve. But I am bit wonder whether how can I implement it without any Collection or intermediate Array.

Question:- Count duplicates from int array without using any Collection or another intermediate Array

Input values:- {7,2,6,1,4,7,4,5,4,7,7,3, 1}  

Output:- Number of duplicates values: 3
         Duplicates values: 7, 4, 1

I have implemented following solution but was not completed one. Any one has some idea? Thanks.

public static void duplicate(int numbers[]) {

    for (int i = 0; i < numbers.length; i++) {

        boolean duplicate = false;
        int j = 0;

        while (j < i){

            if ((i != j) && numbers[i] == numbers[j]) {
                duplicate = true;
            }

            j++;
        }

        if (duplicate) {
            System.out.print(numbers[i] + " ");
        }
    }
}

Answer 1

I think, this is also a way to calculate it:

public class App {
    public static void main(String[] args) {
        Integer[] intArr = { 7, 2, 6, 1, 4, 7, 4 };
        List<Integer> listInt = Arrays.asList(intArr);

        Map<Integer, Integer> map = new HashMap<>();
        Integer dupCount = 0;
        StringBuilder dupvalues = new StringBuilder();

        for (Integer integer : intArr) {
            int times = Collections.frequency(listInt, integer);
            if (map.containsKey(integer)) {
                dupvalues.append(integer).append(",");
                dupCount++;
            } else
                map.put(integer, times);
        }
        System.out.println("There were " + dupCount + " duplicates in the array. The value are : "+dupvalues);
    }
}

Answer 2

The easiest way to solve this problem is to sort the array first, and then just walk through the array counting duplicates as you encounter them:

int[] numbers = new int[]{7,2,6,1,4,7,4,5,4,7,7,3,1};
int temp = 0;

// I chose to do a bubble sort of the array,
// but you are free to use any method you wish (e.g. Arrays.sort)
System.out.print("Duplicates values: ");
for (int i=0; i < numbers.length; ++i) {
    for (int j=1; j < (numbers.length - i); ++j) {
        if (numbers[j-1] > numbers[j]) {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
        }
    }
}


// walk through the sorted array and count duplicates
int numDup = 0, dupCount = 0;
int previous = -1;
for (int i=0; i < numbers.length; ++i) {
    if (numbers[i] == previous) {
        ++numDup;
        if (numDup == 1) {
            ++dupCount;
            if (dupCount == 1) {
                System.out.print(numbers[i]);
            }
            else {
                System.out.print(", " + numbers[i]);
            }
        }
    }
    else {
        previous = numbers[i];
        numDup = 0;
    }
}

System.out.println("\nNumber of duplicates values: " + dupCount);

Output:

Duplicates values: 1, 4, 7
Number of duplicates values: 3

Note that my output order is reverse of what you have, because you need to read through the entire array before you know how many total duplicates you have. Also, I will point out that the only state this solution uses is the input array itself, plus a couple of int varibles here and there.

This code has been tested in IntelliJ and it works correctly.

Answer 3

Below method not use any collection, just use Arrays.sort() method to help sort array into ascending order as default, e.g array = [9,3,9,3,9] will sort into [3,3,9,9,9].If input [9,9,9,9,9], expected result is 1, since only repeated number is 9.If input [9,3,9,3,9,255,255,1], expected result is 3, since repeated numbers are 3,9,255. If input [7,2,6,1,4,7,4,5,4,7,7,3,1], expected result is 3, since repeated numbers are 1,4,7.

public static int findDuplicateCountsInArray(int[] nums) {
    // Sort the input array into default ascending order
    Arrays.sort(nums);
    int prev = nums[0];
    int count = 0;
    // Recording a number already a repeated one
    // e.g [9,9,9] the 3rd 9 will not increase duplicate count again
    boolean numAlreadyRepeated = false;
    for(int i = 1; i < nums.length; i++) {
        if(prev == nums[i] && !numAlreadyRepeated) {
            count++;
            numAlreadyRepeated = true;
        } else if(prev != nums[i]) {
            prev = nums[i];
            numAlreadyRepeated = false;
        }
    }
    return count;
}