右侧更小数

[编程题]右侧更小数

热度指数：572 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组 nums ，请你返回一个新数组 count ，其中 count[i] 是 nums[i] 右侧小于 nums[i] 的元素个数。

数据范围： $1 \le n \le 10^5 \$ ，数组元素值满足 $|nums[i]| \le 10^4 \$

示例1

输入

[9,8,7,6,5]

输出

[4,3,2,1,0]

示例2

输入

[5,7,8,9,6]

输出

[0,1,1,1,0]

算法知识视频讲解

Python2

菜鸡升职记

# -*- 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

发表于 2022-06-23 17:15:20 回复(0)

Java

牛客479467636号

想到用二叉树来解决，在数据平衡的情况下是时间复杂度是O(n*log2n)，空间复杂度是O(n)

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;
        }
    }
}

编辑于 2024-01-10 18:02:01 回复(1)