Painless
Distinct
配列内の個別の値の数を計算します。
タスク説明
関数を書く
class solution {public int solution(int [] A); }
これは、N個の整数で構成される配列Aが与えられた場合、配列Aの個別の値の数を返します。
たとえば、次のような6つの要素で構成される配列Aがあるとします。
例
A [0] = 2 A [1] = 1 A [2] = 1
A [3] = 2 A [4] = 3 A [5] = 1
配列Aには1、2、3の3つの異なる値が表示されるため、関数は3を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- Nは[0..100,000]の範囲内の整数です。
- 配列Aの各要素は、[-1,000,000..1,000,000]の範囲内の整数です。
解く
Program【案1：KV】
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
Report1
Program【案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
著者注
実際の業務では、通常、アルゴリズムを決めることは具体的な業務を考えなければならないでしょう。
- 仮に、ほとんどのシナリオで、データが少ない場合、上記の案1はメモリの節約で更に適用だと思う。
- 逆に、データの量がいつも多い場合は、案2の方が効率的だ。
实际业务中，通常要根据具体情况决定选用哪种算法。当业务中多数情况为少量数据时，上文案1更节约内存；相反，若大多数情况下都是大数据量，那么案2更高效。