leetcode Count of Smaller Numbers After Self

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].

题目地址  leetcode Count of Smaller Numbers After Self

题意:

给定nums数组,求数组中每个元素i的右边比其小的数

思路:

简单的说就是求逆序数。

  1. 使用逆序数有经典的解法为合并排序。
  2. 用Fenwick树  关于Fenwick 树介绍 Binary indexed tree (Fenwick tree) 
    • 简单说就是看当前数在nums中排第几,然后对小于它的数求个数和
    • 具体的做法是先离散化,确定每个数载nums中排到第几 (去重和排序)
    • 然后从右向左扫描,每次统计比其小于1的个数(就是求和),然后把当前的数加入Fenwick中。

 

merge_sort

C++ 

 

 

Binary indexed tree (Fenwick tree)

C++

 

Python

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Count of Smaller Numbers After Self
本文地址:https://www.hrwhisper.me/leetcode-count-of-smaller-numbers-after-self/

您的支持将鼓励我继续创作!

Leetcode , , , . permalink.

4 thoughts on “leetcode Count of Smaller Numbers After Self

  1. 你好博主,能不能对

    for i in xrange(len(nums) – 1, -1, -1):
    ans[i] = tree.sum(dic[nums[i]] – 1)
    tree.add(dic[nums[i]], 1)

    这段循环做个注释呢?
    我看不懂里面的逻辑…..

    • 从右向左扫描,每次统计比其小于1的个数(就是求和),然后把当前的数加入Fenwick中(当前数在序列中排的位置(因为前面离散化了)个数加1)。

Leave a Reply

Your email address will not be published. Required fields are marked *