Carregando

Problema do LeetCode#1365

How Many Numbers Are Smaller Than the Current Number

Resolvido em 1 linguagemJava

Resolver no LeetCode(abre em uma nova aba)

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.

Todos os problemas

Os enunciados dos problemas pertencem ao LeetCode e estão em leetcode.com. Não temos vínculo com o LeetCode.