[Leetcode] How Many Numbers Are Smaller Than the Current Number
3075 ワード
https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
配列.これは、この配列を巡回するときに、自分より小さい値がどれだけあるかを検索する問題です.
[8.12.2.3]の答えは[4.0.1.3]
8未満は4個、1未満は1個、2未満は1個、3未満は3個である.
まず最も簡単な方法は暴力的な方法で巡回することです.
実はこの方法で問題を通過した.
より良い方法はソートを利用することです
実際のテストも成功した.
コードを少し修正しましょう.
この場合、8は巡回したことがないが、以下の要素4と比較して値が異なるため、全長は5〜0〜1であり、8未満の要素は4である.
では7,7,7,7,7は?
この場合、if文は次の要素が一緒に続くため実行されません.
だからtmpの地図には置けないこのため、次のコードを追加しました.
ただし、キーがない場合は、0を加算することで同じ値を処理できます.
思ったほど時間が早くない他の人がどうやって解決したのか探してみます
次は完全なコードです.
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
配列.これは、この配列を巡回するときに、自分より小さい値がどれだけあるかを検索する問題です.
[8.12.2.3]の答えは[4.0.1.3]
8未満は4個、1未満は1個、2未満は1個、3未満は3個である.
まず最も簡単な方法は暴力的な方法で巡回することです.
実はこの方法で問題を通過した.
より良い方法はソートを利用することです
for (int i = 0; i < nums.length; i++) {
int cnt = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] < nums[i]) {
cnt++;
}
}
sol[i] = cnt;
}
このように全体を巡る時間の複雑さはO(N^2)のはずです.実際のテストも成功した.
コードを少し修正しましょう.
Arrays.sort(arr, Comparator.reverseOrder());
Map<Integer, Integer> tmp = new HashMap<>();
for (int i = 0; i < arr.length - 1; i++) {
if (!arr[i].equals(arr[i + 1])) {
tmp.put(arr[i], arr.length - i - 1);
}
}
降順配列の配列をループします.次の要素の値が異なる場合は、配列の長さから任意の数のループを減算します.この場合、8は巡回したことがないが、以下の要素4と比較して値が異なるため、全長は5〜0〜1であり、8未満の要素は4である.
では7,7,7,7,7は?
この場合、if文は次の要素が一緒に続くため実行されません.
だからtmpの地図には置けないこのため、次のコードを追加しました.
for (int i = 0; i < nums.length; i++) {
if (!tmp.containsKey(nums[i])) {
sol[i] = 0;
continue;
}
sol[i] = tmp.get(nums[i]);
}
tmpという名前のマッピングキーで値を取得し、受信した配列をパラメータで巡回します.ただし、キーがない場合は、0を加算することで同じ値を処理できます.
思ったほど時間が早くない他の人がどうやって解決したのか探してみます
次は完全なコードです.
class HowManyNumbersAreSmallerThanTheCurrentNumber {
public static int[] solution(int[] nums) {
Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Comparator.reverseOrder());
int[] sol = new int[nums.length];
Map<Integer, Integer> tmp = new HashMap<>();
for (int i = 0; i < arr.length - 1; i++) {
if (!arr[i].equals(arr[i + 1])) {
tmp.put(arr[i], arr.length - i - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (!tmp.containsKey(nums[i])) {
sol[i] = 0;
continue;
}
sol[i] = tmp.get(nums[i]);
}
return sol;
}
}
Reference
この問題について([Leetcode] How Many Numbers Are Smaller Than the Current Number), 我々は、より多くの情報をここで見つけました https://velog.io/@lkimilhol/Leetcode-How-Many-Numbers-Are-Smaller-Than-the-Current-Numberテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol