Count distinct numbers in an Array in O(n)
by ne on 2021-09-29 under Algo/DS/Problems
To find count of distinct numbers in a given array in O(n) complexity.
The following program achieves this:
package com.codinglords;
/**
* Created by navsoni on 5/8/17.
*/
public class SolutionDistinct {
public int solution(int[] A) {
int max = -1;
for (int i = 0; i < A.length; i++) {
if (A[i] > max) {
max = A[i];
}
}
int[] b = new int[A.length + 1];
for (int i = 0; i < b.length; i++) {
if (i < A.length)
b[A[i]]++;
}
int tr = 0;
for (int i = 0; i < b.length; i++) {
if (b[i] > 0) {
tr++;
}
}
return tr;
}
public static void main(String[] args) {
System.out.println(new SolutionDistinct().solution(new int[]{1, 2, 5, 4, 6, 6, 2}));
}
}
The above program will return 5, which is the count of distinct numbers in the given array, in a O(n) complexity.