给定一个长度为 n 的数组 nums ,请你返回一个新数组 count ,其中 count[i] 是 nums[i] 右侧小于 nums[i] 的元素个数。
数据范围: ,数组元素值满足
# -*- coding: utf-8 -*- import bisect # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: """ 题目: https://www.nowcoder.com/practice/b47363e689bc4a8088a68631d0c2754d?tpId=196&tqId=40450&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 借鉴: 大神:江南蜡笔小新 算法: 题目要求统计每一个nums[i]右侧小于nums[i]的元素的个数,因此我们采取逆序遍历nums,这里我们使用单调递增栈stack,维护逆序遍历序列 具体流程: 逆序遍历nums,对于nums[i]: stack中二分查找插入位置idx,更新count[i] = idx,再将nums[i]插入stack的下标idx位置 注意: 这里要使用list().insert方法,如果使用插入排序,会超时,如下所示,就超时了 # stack.append(nums[i]) # j = len(stack) - 1 # while j > 0 and stack[j] < stack[j - 1]: # 插入排序效率太低 # stack[j], stack[j - 1] = stack[j - 1], stack[j] # j -= 1 复杂度: 时间复杂度:O(nlogn), nlogn为n次二分查找的复杂度 空间复杂度:O(n),辅助空间stack """ def smallerCount(self, nums): # write code here n = len(nums) count, stack = [0] * n, [] for i in range(n - 1, -1, -1): idx = bisect.bisect_left(stack, nums[i]) count[i] = idx stack.insert(idx, nums[i]) return count if __name__ == "__main__": sol = Solution() nums = [9, 8, 7, 6, 5] # nums = [5, 7, 8, 9, 6] res = sol.smallerCount(nums) print res
import java.util.*; public class Solution { public ArrayList<Integer> smallerCount1(ArrayList<Integer> nums) { // 最大最小取平均数 int min = nums.get(0); int max = nums.get(0); for (int num : nums) { if (num < min) { min = num; } else if (num > max) { max = num; } } int mid = (min + max) >> 1; // 设置根节点 TreeNode head = new TreeNode(mid); head.count = 0; for (int i = nums.size() - 1; i >= 0; i--) { // 从右向左遍历 int num = nums.get(i); TreeNode par = head; // 每次从根节点出发 int count = 0; // 计算小于当前数num的值 while (true) { if (num == par.val) { // 当值相等,说明找到了,该节点计数+1 par.count = par.count + 1; // count值加上当前节点的leftCount,leftCount每次添加节点的时候左滑计数,如果当前节点是父节点右孩子,代表: 父节点值 < num < 当前节点值 count = count + par.leftCount; break; } else if (num > par.val) { // 向右滑 count = count + par.leftCount + par.count; // 右滑结算当前节点的leftCount与当前节点的数量 TreeNode right = par.right; if (right == null) { // 右孩子为空说明到头了,初始化右孩子并且设置为count=1(构造设置) right = new TreeNode(num); par.right = right; break; } // 右孩子不为空,右滑继续 par = right; } else { // 小于当前节点值,左滑并且leftCount+1 par.leftCount = par.leftCount + 1; TreeNode left = par.left; if (left == null) { // 如果没左孩子,初始化左孩子,退出循环 left = new TreeNode(num); par.left = left; break; } // 左孩子不为空,继续循环向下 par = left; } } // 设置结果 nums.set(i, count); } return nums; } private static class TreeNode { private int val; private int leftCount; private int count; private TreeNode left; private TreeNode right; public TreeNode(int val) { this.val = val; count = 1; } } }