Painless
Distinct
Calculate the number of individual values in the array.
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:
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
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
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