0%

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct Node {
int val;
int index;
int cnt;
Node(int val, int index) : val(val), index(index), cnt(0) {}
bool operator <= (const Node &node2)const {
return val <= node2.val;
}
};

class Solution {
public:
void combine(vector<Node> &nums, int Lpos, int Lend, int Rend, vector<Node> &temp) {
int Rpos = Lend + 1;
int Tpos = Lpos;
int n = Rend - Lpos + 1;
int t = Rpos;
while (Lpos <= Lend && Rpos <= Rend) {
if (nums[Lpos] <= nums[Rpos]) {
temp[Tpos] = nums[Lpos];
temp[Tpos].cnt += Rpos - t ;
Tpos++; Lpos++;
}
else {
temp[Tpos++] = nums[Rpos++];
}
}

while (Lpos <= Lend) {
temp[Tpos] = nums[Lpos];
temp[Tpos].cnt += Rpos - t;
Tpos++; Lpos++;
}

while (Rpos <= Rend)
temp[Tpos++] = nums[Rpos++];

for (int i = 0; i< n; i++, Rend--)
nums[Rend] = temp[Rend];
}

void merge_sort(vector<Node> & nums, int L, int R, vector<Node> &temp) {
if (L < R) {
int m = (L + R) >> 1;
merge_sort(nums, L, m, temp);
merge_sort(nums, m + 1, R, temp);
combine(nums, L, m, R, temp);
}
}

vector<int> countSmaller(vector<int>& nums) {
vector<Node> mynums;
vector<Node> temp(nums.size(), Node(0, 0));
for (int i = 0; i < nums.size(); i++)
mynums.push_back(Node(nums[i], i));

vector<int> ans(nums.size(), 0);
merge_sort(mynums, 0, nums.size() - 1, temp);

for (int i = 0; i < nums.size(); i++)
ans[mynums[i].index] = mynums[i].cnt;

return ans;
}
};

 

Binary indexed tree (Fenwick tree)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class FenwickTree {
vector<int> sum_array;
int n;
inline int lowbit(int x) {
return x & -x;
}

public:
FenwickTree(int n) :n(n), sum_array(n + 1, 0) {}

void add(int x, int val) {
while (x <= n) {
sum_array[x] += val;
x += lowbit(x);
}
}

int sum(int x) {
int res = 0;
while (x > 0) {
res += sum_array[x];
x -= lowbit(x);
}
return res;
}
};

class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> temp_num = nums;
sort(temp_num.begin(), temp_num.end());
unordered_map<int,int> dic;
for (int i = 0; i < temp_num.size(); i++)
dic[temp_num[i]] = i + 1;

FenwickTree tree(nums.size());
vector<int> ans(nums.size(),0);
for (int i = nums.size() - 1; i >= 0; i--) {
ans[i] = tree.sum(dic[nums[i]] - 1);
tree.add(dic[nums[i]],1);
}
return ans;
}
};

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class FenwickTree(object):
def __init__(self, n):
self.sum_array = [0] * (n + 1)
self.n = n

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

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

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

class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
dic = {}
for i, num in enumerate(sorted(list(set(nums)))):
dic[num] = i + 1
tree = FenwickTree(len(nums))
ans = [0] * len(nums)
for i in xrange(len(nums) - 1, -1, -1):
ans[i] = tree.sum(dic[nums[i]] - 1)
tree.add(dic[nums[i]], 1)
return ans

请我喝杯咖啡吧~