From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/num_smaller_num_self.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) create mode 100644 other/num_smaller_num_self.cpp (limited to 'other/num_smaller_num_self.cpp') 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 countSmaller(vector &nums) { + int n = nums.size(); + vector> vp(n); + vector 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 &count, vector> &vp, int left, int mid, + int right) { + vector> 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 &count, vector> &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); + } +}; -- cgit v1.2.3