In this Leetcode Count of Smaller Numbers After Self problem solution 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].
Problem solution in Python.
class Solution: def countSmaller(self, nums): """ :type nums: List[int] :rtype: List[int] """ tmp = [] ans = [] for i in nums[::-1]: x = bisect.bisect_left(tmp, i) ans.append(x) tmp.insert(x, i) return ans[::-1]
Problem solution in Java.
class Solution { public List<Integer> countSmaller(int[] nums) { ArrayList<Integer>a = new ArrayList<>(); for(int i = 0; i < nums.length; i++){ int count = 0; for(int j = i + 1; j < nums.length; j++){ if(nums[i]> nums[j]){ count++; } } a.add(count); } return a; } }
Problem solution in C++.
vector<int> countSmaller(vector<int>& nums) { vector<int> res(nums.size(), 0), sorted; for (int i = nums.size() - 1; i >= 0; i--) { auto loc = lower_bound(sorted.begin(), sorted.end(), nums[i]); res[i] = loc - sorted.begin(); sorted.insert(loc, nums[i]); } return res; }
Problem solution in C.
struct SearchTree { int val; int count; struct SearchTree* left; struct SearchTree* right; }; struct SearchTree* Insert(struct SearchTree* T, int x, int* count_small) { if(T == NULL) { T = (struct SearchTree*)malloc(sizeof(struct SearchTree)); T->val = x; T->count = 0; T->left = NULL; T->right = NULL; } else { if(x <= T->val) { T->count++; T->left = Insert(T->left, x, count_small); } else { *count_small = *count_small + T->count + 1; T->right = Insert(T->right, x, count_small); } } return T; } int* countSmaller(int* nums, int numsSize, int* returnSize) { *returnSize = numsSize; int *result = (int*)malloc(sizeof(int) * numsSize); struct SearchTree* T = NULL; for(int i = numsSize - 1; i >= 0; --i) { int count_small = 0; T = Insert(T, nums[i], &count_small); result[i] = count_small; } return result; }
0 Comments