[GO] [100%] Distinct (src & junit & author's note)

Painless

Distinct

Calculate the number of individual values ​​in the array.

Task description

Write a function

class solution {public int solution(int [] A); }

It returns the number of individual values ​​in array A, given an array A consisting of N integers.

For example, suppose you have an array A that consists of the following six elements:

Example

  A [0] = 2 A [1] = 1 A [2] = 1
  A [3] = 2 A [4] = 3 A [5] = 1

The function must return 3 because array A shows three different values: 1, 2, and 3.

Write an efficient algorithm for the following assumptions:

• N is an integer in the range [0..100,000].
• Each element of array A is an integer in the range [-1,000,000..1,000,000].

solve

Program [Proposal 1: KV]

DistinctSolution.java

KV

    public int solution(int[] A) {
        java.util.HashMap hm = new java.util.HashMap();
        for (int i = 0; i < A.length; i++) {
            hm.put(A[i], true);
        }
        return hm.size();
    }

Detected time complexity:

O(N*log(N)) or O(N)

jUnit DistinctSolutionTest.java

Report1 trainingC9WE4Y-E39

Program [Proposal 2: Bucket]

Bucket

    public int solution(int[] A) {
        int goal = 0;
        int[] B = new int[2000001];
        for (int a : A) {
            B[1000000 + a]++;
        }

        for (int b : B) {
            if (b > 0) goal++;
        }

        return goal;
    }

Detected time complexity:

O(N*log(N)) or O(N)

Report2 trainingKM7K8S-X97

Author's note

In real life, deciding an algorithm will usually have to consider a concrete task.

• If, in most scenarios, there is little data, I think Plan 1 above is more applicable in terms of memory savings.
• Conversely, if the amount of data is always large, Plan 2 is more efficient.

During the actual business, it is usually necessary to set up a specific situation. In the middle of the business, when a small number of data is installed, the above draft 1 is retained; conflict, the majority of young people are in the lower capital, and the large number of data is installed, and the plan 2 is highly effective.