Leetcode日记–1365. How Many Numbers Are Smaller Than the Current Number

发布于 2020-10-26  109 次阅读


碎碎念:选了个选修课,一学分的,课堂测验竟然占四十分,感觉上当了。做了今天的题,我想该专门复习一下八大排序了,感觉都忘得差不多了。

题目如下

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.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

思路:

方法一:暴力破解

我就只想到这种方法,从某个意义上来说,这好像是空间复杂度最低的解法了。

就是对每个数,都遍历并与其他数比较一次。得到结果并返回。

不过这个方法的时间复杂度为O(n^2)

代码如下:

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n =nums.length;
        int[] res = new int[n];
        for(int i=0;i<n;i++){
            int count = 0;
            for(int j=0;j<n;j++){
                if(j!=i&&nums[j]<nums[i])
                    count+=1;
            }
            res[i]=count;
        }
        return res;
    }
}

方法二:排序(最快的排序为nlogn)

我们可以对数组进行排序,并记录下每个数原来的位置。因为要排序,这里就只能使用二维数组对每个数原来的位置进行存储(dic排序并不方便)。

这里补充一个关于数组排序的小知识(这篇文章讲得还蛮好的,还涉及到了comparator和comparable的区别)。在array自带了sort方法可以进行简单的排序,但是如果我们要自己定义排序比较的方法,则需要传入一个comparator。

Arrays.sort(array, comparator)

比如我们这里要对二维数组,按照其中的第零列进行排序,则需要自己写比较结果如何判定。

在comparator中,实现这个接口的关键就是实现一个compare函数,这个函数的返回值为负,零,正,分别代表第一个对象小于,等于,大于第二个对象。

好了,拓展结束,那么在这个方法中,排序过后,我们遍历二维数组,每个数字前面有多少个与自己值不同的数(可能相等),则那个数原来对应的位置就比多少个数大。

将结果存入res数组并返回即可。

这个方法的空间复杂度为O(n),时间复杂度为O(nlogn),为排序的时间,但是在排序后还要经过n来再次遍历数组。

代码如下:

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n = nums.length;
        int[][] data = new int[n][2];
        for (int i = 0; i < n; i++) {
            data[i][0] = nums[i];
            data[i][1] = i;
        }
        Arrays.sort(data, new Comparator<int[]>() {
            public int compare(int[] data1, int[] data2) {
                return data1[0] - data2[0];
            }
        });

        int[] ret = new int[n];
        int prev = -1;
        for (int i = 0; i < n; i++) {
            if (prev == -1 || data[i][0] != data[i - 1][0]) {
                prev = i;
            }
            ret[data[i][1]] = prev;
        }
        return ret;
    }
}

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/solution/you-duo-shao-xiao-yu-dang-qian-shu-zi-de-shu-zi--2/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)