1. Runtime Distribution
2. Submission Details
3. Description
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].
4. 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.
6. Code
C
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct segmentTree
{
int min;
int max;
int count;
}segmentTree;
segmentTree* tree;
void buildTree(int l, int r, int current)
{
tree[current].min = l;
tree[current].max = r;
tree[current].count = 0;
if(l == r)
{
return;
}
int mid = tree[current].min + tree[current].max >> 1;
buildTree(l, mid, current << 1);
buildTree(mid + 1, r, current << 1 | 1);
}
int query(int num, int current)
{
if(num >= tree[current].max)
{
return tree[current].count;
}
if(num < tree[current].min)
{
return 0;
}
if(num <= tree[current].min + tree[current].max >> 1)
{
return query(num, current << 1);
}
return query(num, current << 1) + query(num, current << 1 | 1);
}
void insert(int num, int current)
{
if(num < tree[current].min || num > tree[current].max)
{
return;
}
tree[current].count++;
if(tree[current].min == tree[current].max)
{
return;
}
int mid = tree[current].min + tree[current].max >> 1;
if(num <= mid)
{
insert(num, current << 1);
}else
{
insert(num, current << 1 | 1);
}
}
int* countSmaller(int* nums, int numsSize, int* returnSize) {
int * result = (int *)malloc(sizeof(int*) * numsSize);
*returnSize = numsSize;
if(numsSize == 0)
{
return result;
}
int max = INT_MIN;
int min = INT_MAX;
for(int i = 0; i< numsSize; i++)
{
min = min > nums[i] ? nums[i] : min;
max = max < nums[i] ? nums[i] : max;
}
tree = (segmentTree*)malloc(sizeof(segmentTree) * (max - min) * 4);
buildTree(min, max, 1);
for(int i = numsSize - 1; i >= 0; i--)
{
result[i] = query(nums[i] -1, 1);
insert(nums[i], 1);
}
return result;
}
int main()
{
int nums[] = { 1,9,7,8,5 };
int *returnSize = malloc(sizeof(int));
int * result= countSmaller(nums, 5, returnSize);
for(int i = 0; i< *returnSize; i++)
{
printf("%d ", result[i]);
}
system("pause");
return 0;
}
Java
import java.util.ArrayList;
import java.util.List;
public class LeetCode0315_2 {
public List<Integer> countSmaller(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return list;
}
int len = nums.length;
int[] idxs = new int[len];
int[] count = new int[len];
for (int i = 0; i < len; i++)
idxs[i] = i;
mergeSort(nums, idxs, 0, len, count);
for (int i : count)
list.add(i);
return list;
}
private void mergeSort(int[] nums, int[] idxs, int start, int end, int[] count) {
if (start + 1 >= end)
return;
int mid = (end - start) / 2 + start;
mergeSort(nums, idxs, start, mid, count);
mergeSort(nums, idxs, mid, end, count);
merge(nums, idxs, start, end, count);
}
private void merge(int[] nums, int[] idxs, int start, int end, int[] count) {
int mid = (end - start) / 2 + start;
int[] tmpIdx = new int[end - start];
int i = start, j = mid, k = 0;
while (k < end - start) {
if (i < mid) {
if (j < end && nums[idxs[j]] < nums[idxs[i]]) {
tmpIdx[k++] = idxs[j++];
} else {
count[idxs[i]] += j - mid;
tmpIdx[k++] = idxs[i++];
}
} else {
tmpIdx[k++] = idxs[j++];
}
}
System.arraycopy(tmpIdx, 0, idxs, start, end - start);
}
public static void main(String[] args) {
int[] nums = { 5, 2, 6, 1 };
LeetCode0315_2 leetcode = new LeetCode0315_2();
List<Integer> result = leetcode.countSmaller(nums);
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i) + " ");
}
}
}
Java
import java.util.LinkedList;
import java.util.List;
public class LeetCode0315_1 {
private int[] tree;
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new LinkedList<Integer>();
if (nums == null || nums.length == 0) {
return result;
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
tree = new int[max - min + 2];
for (int i = nums.length - 1; i >= 0; i--) {
int val = nums[i] - min + 1;
result.add(0, sum(val - 1));
update(val);
}
return result;
}
private int sum(int x) {
int result = 0;
while (x > 0) {
result += tree[x];
x -= lowBit(x);
}
return result;
}
private void update(int x) {
while (x < tree.length) {
tree[x]++;
x += lowBit(x);
}
}
private int lowBit(int x) {
return x & (-x);
}
public static void main(String[] args) {
int[] nums = { 5, 2, 6, 1 };
LeetCode0315_1 leetcode = new LeetCode0315_1();
System.out.println(leetcode.countSmaller(nums));
}
}
Java
import java.util.LinkedList;
import java.util.List;
public class LeetCode0315_4 {
static class Tree {
int left;
int right;
int count;
Tree(int l, int r) {
left = l;
right = r;
}
}
private Tree[] tree;
private int min;
private int max;
public List<Integer> countSmaller(int[] nums) {
List<Integer> result = new LinkedList<Integer>();
if (nums == null || nums.length == 0) {
return result;
}
int len = nums.length;
min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
tree = new Tree[4 * (max - min + 1)];
buildTree(min, max, 1);
for (int i = len - 1; i >= 0; i--) {
result.add(0, sum(nums[i] - 1, 1));
update(nums[i], 1);
}
return result;
}
private void buildTree(int l, int r, int index) {
if (l > r) {
return;
}
tree[index] = new Tree(l, r);
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
buildTree(l, mid, index << 1);
buildTree(mid + 1, r, index << 1 | 1);
}
private void update(int val, int index) {
if (tree[index].left > val || tree[index].right < val) {
return;
}
tree[index].count++;
if (tree[index].left == tree[index].right) {
return;
}
int mid = tree[index].left + ((tree[index].right - tree[index].left) >> 1);
if (val <= mid) {
update(val, index << 1);
} else {
update(val, index << 1 | 1);
}
}
private int sum(int val, int index) {
if (tree[index].right <= val) {
return tree[index].count;
}
if (val < tree[index].left) {
return 0;
}
int mid = tree[index].left + ((tree[index].right - tree[index].left) >> 1);
if (val <= mid) {
return sum(val, index << 1);
} else {
return sum(val, index << 1) + sum(val, index << 1 | 1);
}
}
public static void main(String[] args) {
int[] nums = { 26, 78, 27, 100, 33, 67, 90, 23, 66, 5, 38, 7, 35, 23, 52, 22, 83, 51, 98, 69, 81, 32, 78, 28,
94, 13, 2, 97, 3, 76, 99, 51, 9, 21, 84, 66, 65, 36, 100, 41 };
LeetCode0315_4 leetcode = new LeetCode0315_4();
System.out.println(leetcode.countSmaller(nums));
}
}
Comments | NOTHING