[LeetCode]Count of Smaller Numbers After Self

题目描述:

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:

Given nums = [5, 2, 6, 1]

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.

​Return the array [2, 1, 1, 0].

题目大意:

给定一个整数数组nums,返回一个新的数组counts。数组counts的第i个元素counts[i]表示位于nums[i]右侧且小于nums[i]的元素个数。

实际上就是求逆序对的个数。

测试用例如题目描述。

解题思路:

解法I 树状数组 (Binary Indexed Tree / Fenwick Tree):

1. 对原数组nums进行离散化处理(排序+去重),将nums从实数范围映射到 [1, len(set(nums))],记得到的新数组为iNums

2. 从右向左遍历iNums,对树状数组的iNums[i]位置执行+1操作,然后统计(0, iNums[i])的区间和

也可以用线段树,代码从略。

Python代码:

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        idxes = {}
        for k, v in enumerate(sorted(set(nums))):
            idxes[v] = k + 1
        iNums = [idxes[x] for x in nums]
        ft = FenwickTree(len(iNums))
        ans = [0] * len(nums)
        for i in range(len(iNums) - 1, -1, -1):
            ans[i] = ft.sum(iNums[i] - 1)
            ft.add(iNums[i], 1)
        return ans

class FenwickTree(object):
    def __init__(self, n):
        self.n = n
        self.sums = [0] * (n + 1)

    def add(self, x, val):
        while x <= self.n:
            self.sums[x] += val
            x += self.lowbit(x)

    def lowbit(self, x):
        return x & -x

    def sum(self, x):
        res = 0
        while x > 0:
            res += self.sums[x]
            x -= self.lowbit(x)
        return res

解法II 二叉搜索树 (Binary Search Tree):

树节点TreeNode记录下列信息:

  • 元素值:val
  • 小于该节点的元素个数:leftCnt
  • 节点自身的元素个数:cnt
  • 左孩子:left
  • 右孩子:right

从右向左遍历nums,在向BST插入节点时顺便做统计

Python代码:

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = [0] * len(nums)
        bst = BinarySearchTree()
        for i in range(len(nums) - 1, -1, -1):
            ans[i] = bst.insert(nums[i])
        return ans

class TreeNode(object):
    def __init__(self, val):
        self.leftCnt = 0
        self.val = val
        self.cnt = 1
        self.left = None
        self.right = None

class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def insert(self, val):
        if self.root is None:
            self.root = TreeNode(val)
            return 0
        root = self.root
        cnt = 0
        while root:
            if val < root.val:
                root.leftCnt += 1
                if root.left is None:
                    root.left = TreeNode(val)
                    break
                root = root.left
            elif val > root.val:
                cnt += root.leftCnt + root.cnt
                if root.right is None:
                    root.right = TreeNode(val)
                    break
                root = root.right
            else:
                cnt += root.leftCnt
                root.cnt += 1
                break
        return cnt

解法III 归并排序求逆序数 (Merge Sort):

参考StefanPochmann的答案:https://leetcode.com/discuss/73256/mergesort-solution

Python代码:

class Solution(object):
    def countSmaller(self, nums):
        def sort(enum):
            half = len(enum) / 2
            if half:
                left, right = sort(enum[:half]), sort(enum[half:])
                m, n = len(left), len(right)
                i = j = 0
                while i < m or j < n:
                    if j == n or i < m and left[i][1] <= right[j][1]:
                        enum[i+j] = left[i]
                        smaller[left[i][0]] += j
                        i += 1
                    else:
                        enum[i+j] = right[j]
                        j += 1
            return enum
        smaller = [0] * len(nums)
        sort(list(enumerate(nums)))
        return smaller

 

本文链接:http://bookshadow.com/weblog/2015/12/06/leetcode-count-of-smaller-numbers-after-self/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 大睿-SCTrojan 大睿-SCTrojan 发布于 2016年3月11日 12:38 #

    我有一个问题:BST的Worst Case的时间复杂度是O(N^2)吗?

  2. 在线疯狂 在线疯狂 发布于 2016年3月11日 19:27 #

    对于特定的输入有可能,比如输入一个已经排好序的数组

  3. adiggo adiggo 发布于 2016年3月22日 00:17 #

    是不是应该使用self balanced binary tree.

张贴您的评论