题目大意：给你一个数组，对于数组中的每个元素，返回一共有多少在它之后的元素比它小。
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:
|
1 2 3 4 5 6 |
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++
|
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 |
// 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
|
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 |
// 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++
|
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 |
// 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
|
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 |
// 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); } } } |