算法

您所在的位置：网站首页 › 计算数组中元素个数的方法是 › 算法

算法

2024-06-29 11:54| 来源: 网络整理| 查看: 265

算法-分治法-计算右侧小于当前元素的个数（逆序数） 1 题目概述 1.1 题目出处

https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/

1.2 题目描述

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

示例:

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

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

2 分治法+归并+索引 2.1 解题思路

这个题首先想到的肯定是暴力扫描，即每个数都和右边所有数比，时间复杂度为O(N^2)。

有没有更好的方式呢？试试归并，复杂度O(N*logN)。

拆分成单独元素，合并排序时，记录下每个元素的原始位置以及计算出右侧小于当前元素的个数。

在第二次归并时，因为左侧元素肯定在右侧元素左边（对，这是句废话，但是很重要），且我们的元素已经排序。那么俩边比较的时候，只要左边元素L1比右边元素R1更大，也就意味着左边元素的下一个元素L2也比右边元素R1更大。

通过这个方式，我们就不用比较每个元素了，节约了大量时间。

此外，前面提到过要记录下每个元素的原始位置，这里因为整型元素可能重复，所以我们建立了一个Node来保存他的原始下标，顺带还存放了元素的值和右侧小于当前元素的个数，使用更方便。

2.2 代码 class Solution { // 保存结果数组 private List resultList = new ArrayList(); // Node中存放了元素的值、在原始数组中的下标、右侧小于当前元素的个数 private List nodeList = new ArrayList(); public List countSmaller(int[] nums) { if(nums.length == 0){ return resultList; } // 初始化resultList和nodeList for(int i = 0; i public int val; public int index; public int cnt = 0; public Node(int val, int index){ this.val = val; this.index = index; } } // 拆分计算和归并 private void count(int low, int high){ if(low // 暂存已按大小排序Node，用来复制回原List时使用 ArrayList tmpList = new ArrayList(); int i = low; int j = middle + 1; // 两次遍历之间左边元素计算得到的右侧小于当前元素的个数的增量 int increase = 0; // 标识该次循环是否和上次循环使用同一个左边元素 boolean repeat = false; while(i // 左边小于等于右边元素 if(!repeat){ // 首次遍历该左边元素，此时他更小，就只是加上此前的增量 // 因为增量是前面遍历的更小的左边元素和右边元素比较得到的统计数， // 意味着当前元素也比那些已遍历过的右边元素更大 left.cnt = left.cnt + increase; // 更新该下标元素的`右侧小于当前元素的个数` resultList.set(left.index, left.cnt); }else{ // 重复遍历该元素，说明上一轮是改元素比右边元素大，已经更新过，这里不再更新 repeat = false; } // 将该元素放入tmpList，tmpList是按从小到大排序的list tmpList.add(left); // 准备遍历左边元素的下一个元素 i++; }else{ // 左边大于右边元素 if(!repeat){ // 首次遍历该左边元素，此时他更大，就需要加上此前增量， // 同时还需要加1，因为此时比右边元素大 left.cnt = left.cnt + 1 + increase; }else{ // 重复遍历时，只需要将当前元素的`右侧小于当前元素的个数`加1即可 left.cnt += 1; } // 左边元素比右边元素更大，则每次将增量加一 increase++; // 标记下次还要用自己 repeat = true; // 更新该下标元素的`右侧小于当前元素的个数` resultList.set(left.index, left.cnt); tmpList.add(right); // 准备遍历右边元素的下一个元素 j++; } } if(i Node left = nodeList.get(i++); left.cnt += increase; resultList.set(left.index, left.cnt); tmpList.add(left); } } if(j Node right = nodeList.get(j); resultList.set(right.index, right.cnt); j++; } } // 将临时list复制到原始nodeList，此时nodeList的low->high位置的元素有序 for(int k = 0; k // 保存结果数组 private List resultList = new ArrayList(); // Node中存放了元素的值、在原始数组中的下标、右侧小于当前元素的个数 private List nodeList = new ArrayList(); public List countSmaller(int[] nums) { if(nums.length == 0){ return resultList; } // 初始化resultList和nodeList for(int i = 0; i public int val; public int index; public int cnt = 0; public Node(int val, int index){ this.val = val; this.index = index; } } // 拆分计算和归并 private void count(int low, int high){ if(low // 暂存已按大小排序Node，用来复制回原List时使用 ArrayList tmpList = new ArrayList(); int i = low; int j = middle + 1; // 右侧出列进入临时list的元素数量 int rightCnt = 0; while(i // 左边小于等于右边元素 left.cnt += rightCnt; // 更新该下标元素的`右侧小于当前元素的个数` resultList.set(left.index, left.cnt); // 将该元素放入tmpList，tmpList是按从小到大排序的list tmpList.add(left); // 准备遍历左边元素的下一个元素 i++; }else{ // 左边大于右边元素 rightCnt++; tmpList.add(right); // 准备遍历右边元素的下一个元素 j++; } } // 处理比右边元素都大的左边元素 while(i nodeList.set(low, tmpList.get(k)); } } } 3.3 时间复杂度

在这里插入图片描述

3.4 空间复杂度

O(NlogN)

4 分治法+归并+索引优化二索引数组 4.1 解题思路

优化一中仅仅去掉了repeat判断，但是从执行时间来看其实优化不大。

仔细看看原来代码，需要多次使用Node对象，jvm对对象处理是很花费时间的。

仔细观察Node中的元素：

class Node{ public int val; public int index; public int cnt = 0; public Node(int val, int index){ this.val = val; this.index = index; } }

cnt代表右侧小于当前元素的个数，这个其实可以通过resultList直接维护不需要存

val和index 放置在这里的原因就是index会变，而val是不会变的。那么我们只要能维护一个索引数组，在里面存放元素在原始数组的下标不就行了吗？还能通过这个来找到元素的值，一举两得。

也就是说，要排序时，我们只需要交换这个索引数组就行。

4.2 代码 class Solution { // 保存结果数组 private List resultList = new ArrayList(); // 索引数组，存储每个元素在原始数组中的下标 // 后续我们交换元素时，只改变他们的索引数组 private int[] indexes; // 暂存已按大小排序数字的索引 private int[] tmpIndexes; public List countSmaller(int[] nums) { if(nums.length == 0){ return resultList; } indexes = new int[nums.length]; tmpIndexes = new int[nums.length]; // 初始化resultList和indexes for(int i = 0; i if(low int i = low; int j = middle + 1; // 右侧出列进入临时list的元素数量 int rightCnt = 0; // 记录当前放入tmpIndexes的下标 int k = 0; while(i // 左边小于等于右边元素 // 更新该下标元素的`右侧小于当前元素的个数` resultList.set(indexes[i], resultList.get(indexes[i]) + rightCnt); // 将该元素下标放入tmpIndexes，tmpIndexes是按下标对应元素值从小到大排序的 tmpIndexes[k++] = indexes[i]; // 准备遍历左边元素的下一个元素 i++; }else{ // 左边大于右边元素 rightCnt++; tmpIndexes[k++] = indexes[j]; // 准备遍历右边元素的下一个元素 j++; } } // 处理比右边元素都大的左边元素 while(i indexes[low] = tmpIndexes[l]; } } } 4.3 时间复杂度

O(NlogN)

划分logN，N个元素在这里插入图片描述

4.4 空间复杂度

O(N)

O(N)的indexes和O(N)的tmpIndexes 5 插入排序法 5.1 解题思路

倒序遍历原数组，每次放入一个已按从小到大排序的数组中，只要找到合适位置后再统计前面有几个数就得到了右侧小于当前元素的个数。

这个方法最好理解，但是时间复杂度超过归并排序法。

5.2 代码 public List countSmaller2(int[] nums) { // 保存结果数组 List resultList = new ArrayList(); if(null == nums || nums.length == 0){ return resultList; } for(int i = 0; i sortedList.add(nums[i]); int j = sortedList.size() - 2; for(; j >= 0; j--){ if(nums[i] break; } } resultList.set(i, j + 1); } return resultList; } 5.3 时间复杂度

O(N^2) 在这里插入图片描述太惨了

5.4 空间复杂度

O(N)

6 二叉搜索树(BST) - 循环版本 6.1 解题思路

前面插入排序因为时间复杂度O(N^2)导致超时无法通过，关于排序还可以想到BST、堆等数据结构。

但是这里堆不适用，应该使用BST。

6.2 代码 class Solution { // 保存结果数组 private List resultList = new ArrayList(); class Node{ int val; // 表示左子树有多少节点 int cnt; Node left; Node right; public Node(int val, int cnt){ this.val = val; this.cnt = cnt; } } public List countSmaller(int[] nums) { if(nums.length == 0){ return resultList; } for(int i = 0; i Node newNode = new Node(nums[i], 0); int count = 0; while(currentNode != null){ if(newNode.val > currentNode.val){ // 新节点大于当前节点，需要更新count，加上当前节点的左子树节点总数以及当前节点的数量1 count = count + currentNode.cnt + 1; if(currentNode.right != null){ // 右子树不为空就继续判断右子树 currentNode = currentNode.right; }else{ // 否则就将新节点节点作为左子树 currentNode.right = newNode; // 插入结束，将新节点的`右侧小于当前元素的个数`设为累积到的count resultList.set(i, count); break; } }else{ // 新节点小于等于当前节点，则当前节点左子树节点数量加1 currentNode.cnt++; if(currentNode.left != null){ // 左子树不为空就继续判断左子树 currentNode = currentNode.left; }else{ // 否则就将新节点节点作为左子树 currentNode.left = newNode; // 插入结束，将新节点的`右侧小于当前元素的个数`设为累积到的count resultList.set(i, count); break; } } } currentNode = head; } return resultList; } } 6.3 时间复杂度

平均O(NlogN)

插入logN，一共N个元素在这里插入图片描述

6.4 空间复杂度

O(N)

构建N个Node 7 二叉搜索树(BST) - 递归版本 7.1 解题思路

前面的循环版本有点复杂，我们用递归版本试试。

7.2 代码 class Solution { // 保存结果数组 private List resultList = new ArrayList(); class Node{ // 在原数组下标 int index; int val; // 表示左子树有多少节点 int cnt; Node left; Node right; public Node(int index, int val, int cnt){ this.index = index; this.val = val; this.cnt = cnt; } } private Node insertBst(Node head, Node newNode, int count){ if(head == null){ // head为空，代表之前插入时的节点的子树为空 // 此时结束插入，将当前新节点的统计结果写入resultList resultList.set(newNode.index, count); // 返回当前节点作为之前节点的子树 return newNode; } if(newNode.val > head.val){ // 新节点大于当前节点，需要更新count，加上当前节点的左子树节点总数以及当前节点的数量1 // 然后继续往右子树插入 head.right = insertBst(head.right, newNode, count + head.cnt + 1); }else{ // 新节点小于等于当前节点，则当前节点左子树节点数量加1 head.cnt++; // 继续往左子树插入 head.left = insertBst(head.left, newNode, count); } // 走到这里，说明将新节点插入到本节点的某个子树后边去了， // 所以这里返回当前节点作为父节点的子树，保持不变 return head; } public List countSmaller(int[] nums) { if(nums.length == 0){ return resultList; } // 初始化resultList，以便后面使用 for(int i = 0; i insertBst(head, new Node(i, nums[i], 0), 0); } return resultList; } } 7.3 时间复杂度

平均O(NlogN)

插入logN，一共N个元素在这里插入图片描述

虽然看着简单明了，但还慢了1ms？ 7.4 空间复杂度

O(N)

构建N个Node

【本文地址】

公司简介

联系我们