索引数组_leetcode.315.计算右侧小于当前元素的个数

发表于 | 分类于 ， | 热度: ℃
字数统计: 3.5k | 阅读时长 ≈ 15

🌸题目

🍁给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

1
2
输入: [5,2,6,1]
输出: [2,1,1,0]

解释:

  • 5 的右侧有 2 个更小的元素 (2 和 1).
  • 2 的右侧仅有 1 个更小的元素 (1).
  • 6 的右侧有 1 个更小的元素 (1).
  • 1 的右侧有 0 个更小的元素.

🌸分析

这道题要用排序的思路来解决。快速查找和更新，使用递归或树的结构可以高效实现。

🌸解法一：冒泡/暴力解法

暴力求解，不解释。

稳定的排序方法都可求解这个问题。
冒泡排序每交换一次消除一对逆序，使用一个索引数组记录消除的次数。
时间复杂度O(n2),超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static List<Integer> countSmaller(int[] nums) {
	List<Integer> res = new ArrayList<>();
	
	for(int i = 0; i < nums.length; i++) {
		int flag = nums[i];
		int count = 0;
		for(int j = i + 1; j < nums.length; j++) {
			if(flag > nums[j]) {
				count++;
			}
		}
		if(count != 0) {
			res.add(count);
		}else {
			res.add(0);
		}
	}
	return res;
}

🌸解法二： 插入排序

从右往左进行插入排序，
根据插入的位置计算右边小于该元素的个数。

优化：先使用二分法查找位置，再插入。可以降低内循环查找的时间复杂度O(nlogn)，但是元素交换的次数还是O(n2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> countSmaller(int[] nums) {
    if(nums == null || nums.length == 0) return new LinkedList<>();
    //使用链表头插法
    LinkedList<Integer> res = new LinkedList<>();
    int len = nums.length;
    //反向插入排序
    for(int i = len - 2; i >= 0; i--){
        int j = i + 1, temp = nums[i];
        while(j < len && nums[j] >= temp){
            nums[j - 1] = nums[j];
            j++;
        }
        nums[j - 1] = temp;
        //len - j就表示计数个数
        res.addFirst(len - j);
    }
    //添加最后一个数
    res.add(0);
    //LinkedList也是List
    return res;
}

🌸解法三： 归并排序+索引数组

求解 “逆序对” 的关键在于：当其中一个数字放进最终归并以后的有序数组中的时候，这个数字与之前看过的数字个数（或者是未看过的数字个数）可以直接统计出来，而不必一个一个数”。

回到本题，本题让我们求 “在一个数组的某个元素的右边，比自己小的元素的个数”，因此，我们就 应该在 “前有序数组” 的元素出列的时候，数一数 “后有序数组” 已经出列了多少元素，因为这些已经出列的元素都比当前出列的元素要小（或者等于）。

分析

不过题目中要求我们要具体计算到元素级别。“归并排序” 完成以后，原始数组的位置就已经变化了，因此如何定位元素是关键。

一个元素在算法的执行过程中位置发生变化，我们还想定位它，就是最小索引堆，使用 “索引数组” 的关键在于：

  • “原始数组” 不变，用于比较两个元素的大小，真正位置变换的是 “索引数组”。

为了完成 “索引数组” 的归并，我们还需要一个 “索引数组” 长度的临时数组，把索引数组的值复制过去，比较完成以后，再赋值回 “索引数组”。

注意事项

  • 如果 “前有序数组” 和 “后有序数组” 直接合并的时候，就有序，就不必归并
  • 在 “归并” 的时候，全局使用一个临时存储数组，而不必每一个归并都新建临时的存储空间。
  • 出列一个元素的时候，马上得到右边比自己小的元素的个数，是通过不同的指针之间的距离得到的。

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.ArrayList;
import java.util.List;

public class Solution {

    private int[] temp;
    private int[] counter;
    private int[] indexes;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        temp = new int[len];
        counter = new int[len];
        indexes = new int[len];
        for (int i = 0; i < len; i++) {
            indexes[i] = i;
        }
        mergeAndCountSmaller(nums, 0, len - 1);
        for (int i = 0; i < len; i++) {
            res.add(counter[i]);
        }
        return res;
    }

    /**
     * 针对数组 nums 指定的区间 [l, r] 进行归并排序，在排序的过程中完成统计任务
     *
     * @param nums
     * @param l
     * @param r
     */
    private void mergeAndCountSmaller(int[] nums, int l, int r) {
        if (l == r) {
            // 数组只有一个元素的时候，没有比较，不统计
            return;
        }
        int mid = l + (r - l) / 2;
        mergeAndCountSmaller(nums, l, mid);
        mergeAndCountSmaller(nums, mid + 1, r);
        // 归并排序的优化，同样适用于该问题
        // 如果索引数组有序，就没有必要再继续计算了
        if (nums[indexes[mid]] > nums[indexes[mid + 1]]) {
            mergeOfTwoSortedArrAndCountSmaller(nums, l, mid, r);
        }
    }

    /**
     * [l, mid] 是排好序的
     * [mid + 1, r] 是排好序的
     *
     * @param nums
     * @param l
     * @param mid
     * @param r
     */
    private void mergeOfTwoSortedArrAndCountSmaller(int[] nums, int l, int mid, int r) {
        // 3,4  1,2
        for (int i = l; i <= r; i++) {
            temp[i] = indexes[i];
        }
        int i = l;
        int j = mid + 1;
        // 左边出列的时候，计数
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                indexes[k] = temp[j];
                j++;
            } else if (j > r) {
                indexes[k] = temp[i];
                i++;
                // 此时 j 用完了，[7,8,9 | 1,2,3]
                // 之前的数就和后面的区间长度构成逆序
                counter[indexes[k]] += (r - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) {
                indexes[k] = temp[i];
                i++;
                // 此时 [4,5, 6   | 1,2,3 10 12 13]
                //           mid          j
                counter[indexes[k]] += (j - mid - 1);
            } else {
                // nums[indexes[i]] > nums[indexes[j]] 构成逆序
                indexes[k] = temp[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 6, 1};
        Solution solution = new Solution();
        List<Integer> countSmaller = solution.countSmaller(nums);
        System.out.println(countSmaller);
    }
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution:
    def countSmaller(self, nums):
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        indexes = [i for i in range(size)]
        res = [0 for _ in range(size)]

        self.__helper(nums, 0, size - 1, temp, indexes, res)
        return res

    def __helper(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2

        # 计算一下左边
        self.__helper(nums, left, mid, temp, indexes, res)
        # 计算一下右边
        self.__helper(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序数组
        # [mid+1,right] 后有序数组

        # 先拷贝，再合并

        for i in range(left, right + 1):
            temp[i] = indexes[i]

        l = left
        r = mid + 1
        for i in range(left, right + 1):
            if l > mid:
                # l 用完，就拼命使用 r
                # [1,2,3,4] [5,6,7,8]
                indexes[i] = temp[r]
                r += 1
            elif r > right:
                # r 用完，就拼命使用 l
                # [6,7,8,9] [1,2,3,4]
                indexes[i] = temp[l]
                l += 1
                # 注意：此时前面剩下的数，比后面所有的数都大
                res[indexes[i]] += (right - mid)
            elif nums[temp[l]] <= nums[temp[r]]:
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[l]
                l += 1
                # 注意：
                res[indexes[i]] += (r - mid - 1)
            else:
                assert nums[temp[l]] > nums[temp[r]]
                # 上面两种情况只在其中一种统计就可以了
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[r]
                r += 1

🌸解法四： 二叉搜索树

使用二叉搜索树也可以完成插入并统计的功能，从右往左构建二叉树。
递归实现：
当走到右节点时，

  • 统计根节点和左节点的个数，
  • 继续插入并统计右边是否还有较小值；

当走到左节点或者根节点时，

  • 计数器加一
  • 继续插入并统计左边是否还有较小值。

遍历一遍就可以完成搜索，时间复杂度O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        //初始化
        Integer[] res = new Integer[nums.length];
        Arrays.fill(res, 0);
        List<Integer> list = new ArrayList<>();
        //反向构造二叉树，统计右边的较小数
        TreeNode root = null;
        for (int i = nums.length - 1; i >= 0; i--){
            root = addAndCount(root, new TreeNode(nums[i]), res, i);
        }
        return Arrays.asList(res);
    }

    public TreeNode addAndCount(TreeNode root, TreeNode node, Integer[] res, int i){
        if(root == null){
            root = node;
            return root;
        }
        //根节点的左边保存不大于根节点的元素
        if(root.val >= node.val){ 
            //统计左节点的元素个数
            root.count++;
            root.left = addAndCount(root.left, node, res, i);
        }else{
            //走到右边获取该元素左边的个数（根节点 1 + 左节点 root.count）
            res[i] += 1 + root.count;
            //统计右边是否还有更小的元素
            root.right = addAndCount(root.right, node, res, i);
        }
        return root;
    }
}

class TreeNode{
    int val;
    int count;
    TreeNode left, right;

    public TreeNode(int val){
        this.val = val;
        this.count = 0;
        left = null;
        right = null;
    }
}

🌸解法五： 树状数组

🍁前言

  • 「树状数组」属于高级的数据结构，如果是非竞赛选手和普通公司面试，可以不用掌握
  • 「树状数组」这个数据结构用于高效地解决「前缀和查询」与「单点更新」问题

🍁离散化

首先对数组元素做预处理，这一步叫「离散化」。

  • 考虑到「树状数组」的底层是数组（线性结构），为了避免开辟多余的「树状数组」空间，需要进行「离散化」
  • 「离散化」的作用是：针对数值的大小做一个排名的「映射」，把原始数据映射到 [1, len] 这个区间，这样「树状数组」底层的数组空间会更紧凑，更易于维护。

🍁分析

因为我们关心「当前位置的右边比当前数值小的元素的个数」，因此可以设计如下的算法流程：

  • 从右向左读取排名；
  • 先查询严格小于当前排名的「前缀和」，这里「前缀和」指的是，严格小于当前排名的元素的个数，这一步对应「前缀和查询」；
  • 然后给「当前排名」加 11，这一步对应「单点更新」。

我们根据上面的步骤，针对 [5, 2, 6, 1] 得到排名 [3, 2, 4, 1] ，把具体的计算过程写一下：

  • 第 1 步：读到 1 。
    1 的排名是 1 ，首先先在「树状数组」的下标 1 位置更新，执行的操作是 +1，很明显，在排名 1 之前肯定没有数了（查询排名在 1 之前的数有多少个），所以在结果数组的最后一个位置填 0。
  • 第 2 步：读到 6。
    6 的排名是 4，首先先在「树状数组」的下标 4 位置更新，执行的操作是 +1，接下来在「树状树组」里面执行一次查询，查询在排名 4 之前的元素个数有多少，结果是 1，所以在结果数组的倒数第 2 个位置填 0；
  • 第 3 步：读到 2。
    2 的排名是 2，首先先在「树状数组」的下标 2 位置更新，执行的操作是 +1+1，接下来在「树状树组」里面执行一次查询，查询在排名 2 之前的元素个数有多少，结果是 1，所以在结果数组的倒数第 3 个位置填 11；
  • 第 4 步：读到 5。
    5 的排名是 3，首先先在「树状数组」的下标 3 位置更新，执行的操作是 +1+1，接下来在「树状树组」里面执行一次查询，查询在排名 3 之前的元素个数有多少，结果是 2，所以在结果数组的倒数第 4 个位置填 2。
  • 于是 [2, 1, 1, 0] 即为所求。

🍁参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Solution {

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }

        // 使用二分搜索树方便排序
        Set<Integer> set = new TreeSet();
        for (int i = 0; i < len; i++) {
            set.add(nums[i]);
        }

        // 排名表
        Map<Integer, Integer> map = new HashMap<>();
        int rank = 1;
        for (Integer num : set) {
            map.put(num, rank);
            rank++;
        }

        FenwickTree fenwickTree = new FenwickTree(set.size() + 1);
        // 从后向前填表
        for (int i = len - 1; i >= 0; i--) {
            // 1、查询排名
            rank = map.get(nums[i]);
            // 2、在树状数组排名的那个位置 + 1
            fenwickTree.update(rank, 1);
            // 3、查询一下小于等于“当前排名 - 1”的元素有多少
            res.add(fenwickTree.query(rank - 1));
        }
        Collections.reverse(res);
        return res;
    }


    private class FenwickTree {
        private int[] tree;
        private int len;

        public FenwickTree(int n) {
            this.len = n;
            tree = new int[n + 1];
        }

        // 单点更新：将 index 这个位置 + 1
        public void update(int i, int delta) {
            // 从下到上，最多到 size，可以等于 size
            while (i <= this.len) {
                tree[i] += delta;
                i += lowbit(i);
            }
        }


        // 区间查询：查询小于等于 index 的元素个数
        // 查询的语义是"前缀和"
        public int query(int i) {
            // 从右到左查询
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= lowbit(i);
            }
            return sum;
        }

        public int lowbit(int x) {
            return x & (-x);
        }
    }


    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 6, 1};
        Solution4 solution4 = new Solution4();
        List<Integer> countSmaller = solution4.countSmaller(nums);
        System.out.println(countSmaller);
    }
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from typing import List

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        class FenwickTree:
            def __init__(self, n):
                self.size = n
                self.tree = [0 for _ in range(n + 1)]

            def __lowbit(self, index):
                return index & (-index)

            # 单点更新：将 index 这个位置 + 1
            def update(self, index, delta):
                # 从下到上，最多到 size，可以等于 size
                while index <= self.size:
                    self.tree[index] += delta
                    index += self.__lowbit(index)

            # 区间查询：查询小于等于 index 的元素个数
            # 查询的语义是"前缀和"
            def query(self, index):
                res = 0
                # 从上到下，最少到 1，可以等于 1
                while index > 0:
                    res += self.tree[index]
                    index -= self.__lowbit(index)
                return res

        # 特判
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        # 去重，方便离散化
        s = list(set(nums))

        s_len = len(s)

        # 离散化，借助堆
        import heapq
        heapq.heapify(s)

        rank_map = dict()
        rank = 1
        for _ in range(s_len):
            num = heapq.heappop(s)
            rank_map[num] = rank
            rank += 1

        fenwick_tree = FenwickTree(s_len)

        # 从后向前填表
        res = [None for _ in range(size)]
        # 从后向前填表
        for index in range(size - 1, -1, -1):
            # 1、查询排名
            rank = rank_map[nums[index]]
            # 2、在树状数组排名的那个位置 + 1
            fenwick_tree.update(rank, 1)
            # 3、查询一下小于等于“当前排名 - 1”的元素有多少
            res[index] = fenwick_tree.query(rank - 1)
        return res


if __name__ == '__main__':
    nums = [5, 2, 6, 1]
    solution = Solution()
    result = solution.countSmaller(nums)
    print(result)

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%