LeetCode 315. Count of Smaller Numbers After Self.jpg
LeetCode 315. Count of Smaller Numbers After Self
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.
描述
給定一個(gè)整數(shù)數(shù)組 nums，按要求返回一個(gè)新數(shù)組 counts。數(shù)組 counts 有該性質(zhì)： counts[i] 的值是 nums[i] 右側(cè)小于 nums[i] 的元素的數(shù)量。
示例:
輸入: [5,2,6,1]
輸出: [2,1,1,0]
解釋:
5 的右側(cè)有 2 個(gè)更小的元素 (2 和 1).
2 的右側(cè)僅有 1 個(gè)更小的元素 (1).
6 的右側(cè)有 1 個(gè)更小的元素 (1).
1 的右側(cè)有 0 個(gè)更小的元素.
思路
- 基本思路是我們從后往前遍歷，依次把數(shù)字插入到一個(gè)數(shù)據(jù)結(jié)構(gòu)中，每次插入的時(shí)候返回?cái)?shù)據(jù)結(jié)構(gòu)中比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)，用一個(gè)數(shù)組記錄返回的結(jié)果，這里把記錄結(jié)果的數(shù)組命名為 res。
- 我們最后返回 res 的逆序 「因?yàn)槲覀兪悄嫘虻貜慕o定的數(shù)組中選取數(shù)字的」。
- 關(guān)于數(shù)據(jù)結(jié)構(gòu)的選取：
- 方法一：對(duì)于 python 語(yǔ)言，我們借助 python 自帶的庫(kù)函數(shù) bisect ，通過(guò)數(shù)組來(lái)實(shí)現(xiàn)。有關(guān) bisect 的語(yǔ)法，請(qǐng)參考 這里。
- bisect.bisect_left(list, item) 函數(shù)把 item 插入到 list 中，并且保持 list 是排序的順序，如果 item 已經(jīng)存在于 list 將會(huì)把 item 插入到 list 的最左邊。
- 我們聲明一個(gè)數(shù)組 visited 用于插入元素，我們用 bisect.bisect_left(visited, item) 獲得 item 應(yīng)該插入到 visited 中的位置，把這個(gè)值添加到數(shù)組 res 中。這個(gè)位置的值就是數(shù)組中小于等于 item 元素的個(gè)數(shù)，注意 ：這里一定要用 bisect_left，不能用 bisect_right 因?yàn)槿绻霈F(xiàn)了 重復(fù)的元素，bisect_right 把重復(fù)的元素算在內(nèi) 「因?yàn)?bisect_right 會(huì)插入在重復(fù)元素的右邊」，而題意是找小于當(dāng)前元素的元素個(gè)數(shù)，不包含等于。
- 獲取了元素插入的位置后，我們使用 bisect.insort_right 將元素插入到 visited 中 「使用 bisect.insort_left 也可以」。
- 返回 res 的逆序。
- 方法二：使用二叉搜索數(shù)。有關(guān)二叉搜索數(shù)和平衡二叉搜索樹(shù)請(qǐng)參考這個(gè) 視頻。
- 注意：1. 我們這里的二叉搜索樹(shù)不需要實(shí)現(xiàn)全部功能，這道題里面只需要用到 insert 功能。2. 二叉搜索樹(shù)不存儲(chǔ)重復(fù)的元素。
- 二叉樹(shù)的節(jié)點(diǎn)我們聲明五個(gè)變量：1. value 用于存儲(chǔ)節(jié)點(diǎn)的值。 2. count 用于表示當(dāng)前值出現(xiàn)的次數(shù)，默認(rèn)為1。3. smaller 表示比當(dāng)前節(jié)點(diǎn)值小的節(jié)點(diǎn)的個(gè)數(shù)。 4. left_child 左子樹(shù)。5. right_child 右子樹(shù)。
- 在向二叉樹(shù)中插入值 value 的時(shí)候，如果插入的值比當(dāng)前的節(jié)點(diǎn)小，當(dāng)前節(jié)點(diǎn)的 smaller 自增一次，并且將 value 插入到左子樹(shù)中，在最后創(chuàng)建新節(jié)點(diǎn)的后返回 0。
- 如果插入的值比當(dāng)前節(jié)點(diǎn)的值大，我們記下當(dāng)前位置比 value 小的節(jié)點(diǎn)個(gè)數(shù) count + smaller，然后將 value 插入到當(dāng)前節(jié)點(diǎn)的右子樹(shù)中，在最后創(chuàng)建新節(jié)點(diǎn)后返回 count + smaller。
- 如果要插入的元素的值和當(dāng)前節(jié)點(diǎn)的值相等，返回 當(dāng)前節(jié)點(diǎn)的 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 內(nèi)部二分搜索庫(kù)
import bisect
# 二叉搜索樹(shù)的節(jié)點(diǎn)
class Node:
def __init__(self, value=None):
# 節(jié)點(diǎn)的值
self.value = value
# 二叉搜索樹(shù)不存儲(chǔ)重復(fù)節(jié)點(diǎn)，我們用 count 來(lái)存值出現(xiàn)的次數(shù)
self.count = 1
# 比當(dāng)前元素值小的元素個(gè)數(shù)
self.smaller = 0
# 左子樹(shù)
self.left_child = None
# 右子樹(shù)
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):
# 如果當(dāng)前需要插入的值比當(dāng)前節(jié)點(diǎn)的值小
if value < node.value:
# node.smaller 自增一次
node.smaller += 1
# 如果當(dāng)前節(jié)點(diǎn)還沒(méi)有左子樹(shù)
if node.left_child == None:
# 創(chuàng)建一個(gè)新的節(jié)點(diǎn)
node.left_child = Node(value)
# 返回 0 表示比當(dāng)前插入元素還小的元素個(gè)數(shù)為 0
return 0
else:
# 否則將當(dāng)前元素插入到當(dāng)前節(jié)點(diǎn)的左子樹(shù)
return self._insert(value, node.left_child)
# 如果當(dāng)前需要插入的值比當(dāng)前節(jié)點(diǎn)的值大
elif value > node.value:
# smaller 表示當(dāng)前節(jié)點(diǎn)連接的左子樹(shù)的所有節(jié)點(diǎn)個(gè)數(shù)
# 左子樹(shù)的所有節(jié)點(diǎn)值一定比當(dāng)前節(jié)點(diǎn)小
# 由于樹(shù)是動(dòng)態(tài)創(chuàng)建的，因此比 value 值小的節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)的左子樹(shù)和當(dāng)前節(jié)點(diǎn)的右子樹(shù)的左子樹(shù)中
smaller = node.count + node.smaller
# 如果當(dāng)前節(jié)點(diǎn)還沒(méi)有右子樹(shù)
if node.right_child == None:
# 創(chuàng)建一個(gè)新的節(jié)點(diǎn)
node.right_child = Node(value)
# 返回 smaller
return smaller
else:
# 如果有右子樹(shù)，說(shuō)明當(dāng)前值不僅比當(dāng)前節(jié)點(diǎn)的左子樹(shù)的節(jié)點(diǎn)值大
# 有可能比當(dāng)前節(jié)點(diǎn)的右子樹(shù)的左子樹(shù)節(jié)點(diǎn)大，
# smaller 僅僅記錄了當(dāng)前節(jié)點(diǎn)的左子樹(shù)
# 返回 smaller + 當(dāng)前節(jié)點(diǎn)右子樹(shù)中比要插入的值小的元素個(gè)數(shù)
return smaller + self._insert(value, node.right_child)
else:
# 如果當(dāng)前要插入的值已經(jīng)在二叉搜索樹(shù)中，count 自增一次
node.count += 1
# 返回 node.smaller
return node.smaller
class Solution:
# 第一種方法，我們借助二叉搜索樹(shù)實(shí)現(xiàn)
# 需要自己實(shí)現(xiàn)二叉搜索數(shù) 「只需要實(shí)現(xiàn)插入部分，查找和刪除在這里用不到」
def countSmaller(self, nums: 'List[int]') -> 'List[int]':
Tree = BinarySearchTree()
res = []
for num in nums[::-1]:
# 從后向前插入，每次插入一個(gè)值，返回樹(shù)中比當(dāng)前元素小的元素的個(gè)數(shù)
res.append(Tree.insert(num))
# 因?yàn)槲覀兪菑暮竺嫦蚯安迦氲?，所以需要返回逆序的結(jié)果數(shù)組
return res[::-1]
# 方法二，借助python 二分搜索庫(kù)
def countSmaller2(self, nums: 'List[int]') -> 'List[int]':
res, visited = [], []
for num in nums[::-1]:
# num 插入位置的索引就是比他小的元素的個(gè)數(shù)
res.append(bisect.bisect_left(visited, num))
# 將 num 元素插入到 visited 數(shù)組中
# 這里使用 insort_right 或者 insort_left 均可
bisect.insort_right(visited, num)
# 返回逆序的結(jié)果數(shù)組
return res[::-1]
源代碼文件在 這里。
?本文首發(fā)于 何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來(lái)源，作者信息和本聲明.
