Problema do LeetCode#1365
How Many Numbers Are Smaller Than the Current Number
Resolvido em 1 linguagemJava
Solução
45 linhas
1class Solution {
2 // time O(n)
3 // space O(1)
4 public int[] smallerNumbersThanCurrent(int[] nums) {
5 // Due to the constraint 0 <= nums[i] <= 100, we can use an array
6 // to keep track of the number of smaller numbers for counts[nums[i]].
7 int[] counts = new int[102];
8
9 for (int i = 0; i < nums.length; i++) {
10 // store count one number to the right to simplify code later on.
11 // because we allocate room for index 101, it won't go out of bounds.
12 counts[nums[i] + 1]++;
13 }
14
15 for (int i = 1; i < counts.length; i++) {
16 counts[i] += counts[i - 1];
17 }
18 // afterward: counts[i] gives count of numbers < i
19
20 // note: if you don't want to mutate nums,
21 // create an ans array and set & return that instead
22 for (int i = 0; i < nums.length; i++) {
23 nums[i] = counts[nums[i]];
24 }
25
26 return nums;
27 }
28
29 // time O(n^2)
30 // space O(n)
31 // public int[] smallerNumbersThanCurrent(int[] nums) {
32 // int[] counts = new int[nums.length];
33
34 // for (int i = 0; i < nums.length; i++) {
35 // int n = nums[i];
36 // for (int j = 0; j < nums.length; j++) {
37 // if (i != j && nums[j] < n) {
38 // counts[i]++;
39 // }
40 // }
41 // }
42
43 // return counts;
44 // }
45}Quer uma explicação desta solução em Java?
Receba uma explicação passo a passo da ideia por trás do código.
Os enunciados dos problemas pertencem ao LeetCode e estão em leetcode.com. Não temos vínculo com o LeetCode.