题目大意：给你一个数组，对于数组中的每个元素，返回一共有多少在它之后的元素比它小。

Problem:

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

Idea:

Fenwick Tree / Binary Indexed Tree

BST

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

// Author: Huahua

// Runnning time: 32 ms

// Time complexity: O(nlogn)

// Space complexity: O(k), k is the number unique elements

class FenwickTree {

public:

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

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) { return x & (-x); }

vector<int> sums_;

};

class Solution {

public:

vector<int> countSmaller(vector<int>& nums) {

// Sort the unique numbers

set<int> sorted(nums.begin(), nums.end());

// Map the number to its rank

unordered_map<int, int> ranks;

int rank = 0;

for (const int num : sorted)

ranks[num] = ++rank;

vector<int> ans;

FenwickTree tree(ranks.size());

// Scan the numbers in reversed order

for (int i = nums.size() - 1; i >= 0; --i) {

// Chechk how many numbers are smaller than the current number.

ans.push_back(tree.query(ranks[nums[i]] - 1));

// Increse the count of the rank of current number.

tree.update(ranks[nums[i]], 1);

}

std::reverse(ans.begin(), ans.end());

return ans;

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

private static int lowbit(int x) { return x & (-x); }

class FenwickTree {

private int[] sums;

public FenwickTree(int n) {

sums = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums.length) {

sums[i] += delta;

i += lowbit(i);

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums[i];

i -= lowbit(i);

}

return sum;

}

};

public List<Integer> countSmaller(int[] nums) {

int[] sorted = Arrays.copyOf(nums, nums.length);

Arrays.sort(sorted);

Map<Integer, Integer> ranks = new HashMap<>();

int rank = 0;

for (int i = 0; i < sorted.length; ++i)

if (i == 0 || sorted[i] != sorted[i - 1])

ranks.put(sorted[i], ++rank);

FenwickTree tree = new FenwickTree(ranks.size());

List<Integer> ans = new ArrayList<Integer>();

for (int i = nums.length - 1; i >= 0; --i) {

int sum = tree.query(ranks.get(nums[i]) - 1);

ans.add(tree.query(ranks.get(nums[i]) - 1));

tree.update(ranks.get(nums[i]), 1);

}

Collections.reverse(ans);

return ans;

}

Solution 2: BST

C++

// Author: Huahua

// Running time: 26 ms

struct BSTNode {

int val;

int count;

int left_count;

BSTNode* left;

BSTNode* right;

BSTNode(int val): val(val), count(1), left_count(0), left{nullptr}, right{nullptr} {}

~BSTNode() { delete left; delete right; }

int less_or_equal() const { return count + left_count; }

};

class Solution {

public:

vector<int> countSmaller(vector<int>& nums) {

if (nums.empty()) return {};

std::reverse(nums.begin(), nums.end());

std::unique_ptr<BSTNode> root(new BSTNode(nums[0]));

vector<int> ans{0};

for (int i = 1; i < nums.size(); ++i)

ans.push_back(insert(root.get(), nums[i]));

std::reverse(ans.begin(), ans.end());

return ans;

}

private:

// Returns the number of elements smaller than val under root.

int insert(BSTNode* root, int val) {

if (root->val == val) {

++root->count;

return root->left_count;

} else if (val < root->val) {

++root->left_count;

if (root->left == nullptr) {

root->left = new BSTNode(val);

return 0;

}

return insert(root->left, val);

} else {

if (root->right == nullptr) {

root->right = new BSTNode(val);

return root->less_or_equal();

}

return root->less_or_equal() + insert(root->right, val);

}

};

Java

// Author: Huahua

// Running time: 10 ms

class Solution {

class Node {

int val;

int count;

int left_count;

Node left;

Node right;

public Node(int val) { this.val = val; this.count = 1; }

public int less_or_equal() { return count + left_count; }

}

public List<Integer> countSmaller(int[] nums) {

List<Integer> ans = new ArrayList<>();

if (nums.length == 0) return ans;

int n = nums.length;

Node root = new Node(nums[n - 1]);

ans.add(0);

for (int i = n - 2; i >= 0; --i)

ans.add(insert(root, nums[i]));

Collections.reverse(ans);

return ans;

}

private int insert(Node root, int val) {

if (root.val == val) {

++root.count;

return root.left_count;

} else if (val < root.val) {

++root.left_count;

if (root.left == null) {

root.left = new Node(val);

return 0;

}

return insert(root.left, val);

} else {

if (root.right == null) {

root.right = new Node(val);

return root.less_or_equal();

}

return root.less_or_equal() + insert(root.right, val);

}

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏

花花酱 LeetCode 315. Count of Smaller Numbers After Self

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

Java

Solution 2: BST

C++

Java

Be First to Comment

Leave a Reply Cancel reply