LeetCode 315. Count of Smaller Numbers After Self

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

v2-e606225040d95e0a26dfdd5e30f3b49b_1440w.jpg

Description



You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].


Example:


Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.


描述



给定一个整数数组 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 个更小的元素.


思路



  • 基本思路是我们从后往前遍历,依次把数字插入到一个数据结构中,每次插入的时候返回数据结构中比这个数小的数的个数,用一个数组记录返回的结果,这里把记录结果的数组命名为 res。
  • 我们最后返回 res 的逆序 「因为我们是逆序地从给定的数组中选取数字的」。
  • 关于数据结构的选取:
  • 方法一:对于 python 语言,我们借助 python 自带的库函数 bisect ,通过数组来实现。有关 bisect 的语法,请参考 这里
  • bisect.bisect_left(list, item) 函数把 item 插入到 list 中,并且保持 list 是排序的顺序,如果 item 已经存在于 list 将会把 item 插入到 list 的最左边。
  • 我们声明一个数组 visited 用于插入元素,我们用 bisect.bisect_left(visited, item) 获得 item 应该插入到 visited 中的位置,把这个值添加到数组 res 中。这个位置的值就是数组中小于等于 item 元素的个数,注意 :这里一定要用 bisect_left,不能用 bisect_right 因为如果出现了 重复的元素,bisect_right 把重复的元素算在内 「因为 bisect_right 会插入在重复元素的右边」,而题意是找小于当前元素的元素个数,不包含等于。
  • 获取了元素插入的位置后,我们使用 bisect.insort_right 将元素插入到 visited 中 「使用 bisect.insort_left 也可以」。
  • 返回 res 的逆序。
  • 方法二:使用二叉搜索数。有关二叉搜索数和平衡二叉搜索树请参考这个 视频
  • 注意:1. 我们这里的二叉搜索树不需要实现全部功能,这道题里面只需要用到 insert 功能。2. 二叉搜索树不存储重复的元素。
  • 二叉树的节点我们声明五个变量:1. value 用于存储节点的值。 2. count 用于表示当前值出现的次数,默认为1。3. smaller 表示比当前节点值小的节点的个数。 4. left_child 左子树。5. right_child 右子树。
  • 在向二叉树中插入值 value 的时候,如果插入的值比当前的节点小,当前节点的 smaller 自增一次,并且将 value 插入到左子树中,在最后创建新节点的后返回 0。
  • 如果插入的值比当前节点的值大,我们记下当前位置比 value 小的节点个数 count + smaller,然后将 value 插入到当前节点的右子树中,在最后创建新节点后返回 count + smaller。
  • 如果要插入的元素的值和当前节点的值相等,返回 当前节点的 smaller 值。


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-20 13:55:15
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-21 11:48:51
# python 内部二分搜索库
import bisect
# 二叉搜索树的节点
class Node:
    def __init__(self, value=None):
        # 节点的值
        self.value = value
        # 二叉搜索树不存储重复节点,我们用 count 来存值出现的次数
        self.count = 1
        # 比当前元素值小的元素个数
        self.smaller = 0
        # 左子树
        self.left_child = None
        # 右子树
        self.right_child = None
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
            return 0
        else:
            return self._insert(value, self.root)
    def _insert(self, value, node):
        # 如果当前需要插入的值比当前节点的值小
        if value < node.value:
            # node.smaller 自增一次
            node.smaller += 1
            # 如果当前节点还没有左子树
            if node.left_child == None:
                # 创建一个新的节点
                node.left_child = Node(value)
                # 返回 0  表示比当前插入元素还小的元素个数为 0
                return 0
            else:
                # 否则将当前元素插入到当前节点的左子树
                return self._insert(value, node.left_child)
        # 如果当前需要插入的值比当前节点的值大
        elif value > node.value:
            # smaller 表示当前节点连接的左子树的所有节点个数
            # 左子树的所有节点值一定比当前节点小
            # 由于树是动态创建的,
            # 因此比 value 值小的节点在当前节点的左子树和当前节点的右子树的左子树中
            smaller = node.count + node.smaller
            # 如果当前节点还没有右子树
            if node.right_child == None:
                # 创建一个新的节点
                node.right_child = Node(value)
                # 返回 smaller
                return smaller
            else:
                # 如果有右子树,说明当前值不仅比当前节点的左子树的节点值大
                # 有可能比当前节点的右子树的左子树节点大,
                # smaller 仅仅记录了当前节点的左子树
                # 返回 smaller + 当前节点右子树中比要插入的值小的元素个数
                return smaller + self._insert(value, node.right_child)
        else:
            # 如果当前要插入的值已经在二叉搜索树中,count 自增一次
            node.count += 1
            # 返回 node.smaller
            return node.smaller
class Solution:
    # 第一种方法,我们借助二叉搜索树实现
    # 需要自己实现二叉搜索数 「只需要实现插入部分,查找和删除在这里用不到」
    def countSmaller(self, nums: 'List[int]') -> 'List[int]':
        Tree = BinarySearchTree()
        res = []
        for num in nums[::-1]:
            # 从后向前插入,每次插入一个值,返回树中比当前元素小的元素的个数
            res.append(Tree.insert(num))
        # 因为我们是从后面向前插入的,所以需要返回逆序的结果数组
        return res[::-1]
    # 方法二,借助python 二分搜索库
    def countSmaller2(self, nums: 'List[int]') -> 'List[int]':
        res, visited = [], []
        for num in nums[::-1]:
            # num 插入位置的索引就是比他小的元素的个数
            res.append(bisect.bisect_left(visited, num))
            # 将 num 元素插入到 visited 数组中 
            # 这里使用 insort_right 或者 insort_left 均可
            bisect.insort_right(visited, num)
        # 返回逆序的结果数组
        return res[::-1]


源代码文件在 这里


目录
相关文章
|
9月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
12月前
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers
LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String
LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 357. Count Numbers with Unique Digits
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。
68 0
LeetCode 357. Count Numbers with Unique Digits
LeetCode 238. Product of Array Except Self
给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
66 0
LeetCode 238. Product of Array Except Self
|
存储
Leetcode-Medium 2. Add Two Numbers
Leetcode-Medium 2. Add Two Numbers
54 0
Leetcode-Easy 985. Sum of Even Numbers After Queries
Leetcode-Easy 985. Sum of Even Numbers After Queries
83 0