diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/num_smaller_num_self.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/num_smaller_num_self.cpp')
-rw-r--r-- | other/num_smaller_num_self.cpp | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/other/num_smaller_num_self.cpp b/other/num_smaller_num_self.cpp new file mode 100644 index 0000000..49b3ed3 --- /dev/null +++ b/other/num_smaller_num_self.cpp @@ -0,0 +1,44 @@ +#include "leetcode.h" + +class Solution { +public: + vector<int> countSmaller(vector<int> &nums) { + int n = nums.size(); + vector<pair<int, int>> vp(n); + vector<int> count(n, 0); + for (int i = 0; i < n; i++) + vp[i] = make_pair(nums[i], i); + sort(count, vp, 0, n - 1); + return count; + } + +private: + void merge(vector<int> &count, vector<pair<int, int>> &vp, int left, int mid, + int right) { + vector<pair<int, int>> tmp(right - left + 1); + int i = left, j = mid + 1, k = 0; + while (i <= mid && j <= right) { + if (vp[i].first <= vp[j].first) + tmp[k++] = vp[j++]; + else { + count[vp[i].second] += right - j + 1; + tmp[k++] = vp[i++]; + } + } + while (i <= mid) + tmp[k++] = vp[i++]; + while (j <= right) + tmp[k++] = vp[j++]; + for (int i = left; i <= right; i++) + vp[i] = tmp[i - left]; + } + void sort(vector<int> &count, vector<pair<int, int>> &vp, int left, + int right) { + if (left >= right) + return; + int mid = left + (right - left) / 2; + sort(count, vp, left, mid); + sort(count, vp, mid + 1, right); + merge(count, vp, left, mid, right); + } +}; |