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

Painless

Distinct

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

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:


solve

image.png

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.

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.


Recommended Posts

[100%] Distinct (src & junit & author's note)
[100%] MissingInteger (src & junit & author's note)
[100%] [GenomicRangeQuery] (src & junit & author's note)
[100%] MaxCounters (src & junit & author's note)
[100%] CountDiv (src & junit & author's note)
[100%] CyclicRotation (src & jUnit)
[100%] PermMissingElem (src & jUnit)
[100%] FrogRiverOne (src & jUnit)
[100%] OddOccurrencesInArray (src & jUnit)
[100%] MinAvgTwoSlice (src & junit)
[100%] PassingCars (src & junit)
[100%] PermCheck (src & junit)
[100%] TapeEquilibrium (src & jUnit)
[100%] MaxProductOfThree (src & jUnit)
[100%] BinaryGap (src & jUnit)
Java JUnit brief note