0%

leetcode每日一题-计算右侧小于当前元素的个数

Posted on Edited on In ,

计算右侧小于当前元素的个数

image1

方法一：暴力法优化（二分查找）

直观思路就是遍历到第$i$个数的时候，遍历下标$[i+1,nums.length-1]$的数并计算个数，但直接这么做会超时，我们使用二分查找进行优化。思路就是逆序遍历$nums$数组，我们新建一个排序的数组$sortnums$用来保存遍历过的数，每次遍历到一个数$nums[i]$，首先在$sortnums$查找$nums[i]$在该排序数组中的位置$index$，那么此时在$nums[i]$右边比$nums[i]$小的数就有$index$个。之后我们将$nums[i]$插入到$index$处，注意此处的二分查找需要寻找左边界。至于怎么寻找左边界，可以看我的另一篇博客二分查找算法总结。

1
class Solution {
2
    public List<Integer> countSmaller(int[] nums) {
3
        if(nums==null || nums.length==0){
4
            return new ArrayList<Integer>();
5
        }
6
        int n = nums.length;
7
        Integer[] ans = new Integer[n];
8
        List<Integer> list = new ArrayList<>();
9
        for(int i=n-1; i>=0; i--){
10
            if(i==n-1){
11
                list.add(nums[i]);
12
                ans[i] = 0;
13
            }else{
14
                int index = binarySearch(list, nums[i]);
15
                list.add(index, nums[i]);
16
                ans[i] = index;
17
            }
18
        }
19
        return Arrays.asList(ans);
20
    }
21
22
    public int binarySearch(List<Integer> list, int target){
23
        int left = 0;
24
        int right = list.size()-1;
25
        while(left <= right){
26
            int mid = left + (right-left)/2;
27
            if(list.get(mid) >= target){
28
                right = mid-1;
29
            }else{
30
                left = mid+1;
31
            }
32
        }
33
        return left;
34
    }
35
}

复杂度分析：

  • 时间复杂度：$O(n*(n+logn))$，二分查找复杂度为$logn$，$list$插入复杂度为$n$。
  • 空间复杂度：$O(n)$。

方法二：归并排序

这题和统计逆序数有点类似，可以使用归并排序解决。在进行归并排序的时候，用两个指针i和j分别指向leftPart和rightPart的开头，左右两部分都是降序的，即从大到小排序。如果指针j指向的元素大于等于指针i指向的元素，就将右边的元素归并。如果指针j指向的元素小于指针i指向的元素，那么就将左边的元素归并，此时可以知道在右半部分比指针i指向的元素小的个数应该为right-j+1。在这个过程中，就可以统计出右侧小于当前元素的个数。注意，在这里我们需要一个索引数组来保存原始数据在原始数组中的下标，在进行归并的时候我们是对索引数组进行操作，而不是原始数组。

1
class Solution{
2
    private int[] index;
3
    private int[] helper;
4
    private int[] count;
5
    public List<Integer> countSmaller(int[] nums){
6
        if(nums==null || nums.length==0){
7
            return new ArrayList<Integer>();
8
        }
9
        List<Integer> ans = new ArrayList<>();
10
        int n = nums.length;
11
        index = new int[n];
12
        helper = new int[n];
13
        count = new int[n];
14
        for(int i=0; i<n; i++){
15
            index[i] = i;
16
        }
17
        merge(nums, 0, n-1);
18
        for(int i=0; i<n; i++){
19
            ans.add(i, count[i]);
20
        }
21
        return ans;
22
    }
23
24
    public void merge(int[] nums, int left, int right){
25
        if(left >= right){
26
            return;
27
        }
28
        int mid = left + (right-left)/2;
29
        merge(nums, left, mid);
30
        merge(nums, mid+1, right);
31
32
        int i=left;
33
        int j=mid+1;
34
        int k=left;
35
        while(i<=mid && j<=right){
36
            if(nums[index[i]] <= nums[index[j]]){
37
                helper[k++] = index[j++];
38
            }else{
39
                count[index[i]] += right-j+1;
40
                helper[k++] = index[i++];
41
            }
42
        }
43
        while(i <= mid){
44
            helper[k++] = index[i++];
45
        }
46
        while(j <= right){
47
            helper[k++] = index[j++];
48
        }
49
        for(int m=left; m<=right; m++){
50
            index[m] = helper[m];
51
        }
52
    }
53
}

复杂度分析：

  • 时间复杂度：$O(nlogn)$，归并排序的时间复杂度为$O(nlogn)$。
  • 空间复杂度：$O(n)$。

方法三：离散化树状数组

树状数组是一种可以动态维护序列前缀和的数据结构，它可以进行单点更新和区间查询，在此题中，我们可以逆序遍历数组nums，得到它的索引并在树状数组中进行区间查询query(i)，得到的结果就是右侧小于该数的个数，并将nums[i]插入树状数组，进行单点更新update(i,1)。由于树状数组的修改和查询时间都为$O(logn)$，所以可以有效节约时间。

另一方面考虑到nums数组中不是所有的数都有，如果数组很大，但是只有几个数不为0，那么将浪费很大的空间，所以我们可以进行离散化数组节省空间，离散化之后我们可以得到某个数在数组中的相对排名并作为索引。

1
class Solution {
2
3
    private int[] a;
4
5
    public List<Integer> countSmaller(int[] nums){
6
        List<Integer> ans = new ArrayList<>();
7
        discretization(nums);
8
        int n = a.length;
9
        int numslen = nums.length;
10
        IntegerBIT bit = new IntegerBIT(numslen);
11
        for(int i=0; i<numslen; i++){
12
            bit.update(i, 0);
13
        }
14
        for(int i=numslen-1; i>=0; i--){
15
            int id = getId(nums[i]);
16
            ans.add(bit.query(id-1));
17
            bit.update(id, 1);
18
        }
19
        Collections.reverse(ans);
20
        return ans;
21
    }
22
23
    public int getId(int x){
24
        return Arrays.binarySearch(a, x) + 1;
25
    }
26
27
    public void discretization(int[] nums){
28
        Set<Integer> set = new HashSet<>();
29
        for(int num:nums){
30
            set.add(num);
31
        }
32
        int size = set.size();
33
        a = new int[size];
34
        int index = 0;
35
        for(int num : set){
36
            a[index++] = num;
37
        }
38
        Arrays.sort(a);
39
    }
40
}
41
42
public class IntegerBIT{
43
    int[] data;
44
    int n;
45
46
    public IntegerBIT(int n){
47
        this.n = n;
48
        data = new int[n+1];
49
    }
50
51
    public int lowbit(int x){
52
        return x & (-x);
53
    }
54
55
    public void update(int i, int mod){
56
        if(i<=0){
57
            return;
58
        }
59
        while(i <= n){
60
            data[i] += mod;
61
            i += lowbit(i);
62
        }
63
    }
64
65
    public int query(int i){
66
        int sum = 0;
67
        while(i > 0){
68
            sum += data[i];
69
            i -= lowbit(i);
70
        }
71
        return sum;
72
    }
73
}

复杂度分析：

  • 时间复杂度：$O(nlogn)$。
  • 空间复杂度：$O(n)$。