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.