• 题目
• 大致意思
• 解决方案
• 源代码

题目

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:

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].

大致意思

• 给定一个数组，判断每个数字的右边有几个比它小的数字。

nums = [5, 2, 6, 1]

5的右边有 (2 和 1).
2的右边有 (1).
6的右边有 (1).
1的右边没有.
所以返回的数组是 array [2, 1, 1, 0].

解决方案

• 我们可以从后往前遍历，然后依次把数组插入到一个新数组中，然后通过二分法去查找新的数应该在的位置，根据新的数组来判断应该有多少个小于它的数字

源代码

var countSmaller = function(nums) {
  var array = [];
  var arr = [];
  var length = nums.length;
  var index = 0;
  for (var i = length - 1; i >= 0; i--) {
    var d = nums[i];
    index = binarySearch(arr, d);
    inserIndex = index;

    while (arr[inserIndex] === d) {
      inserIndex--;
    }
    if (index !== inserIndex) inserIndex++;
    arr.splice(index, 0, d);
    array.unshift(inserIndex);
  }
  return array;
};

function binarySearch(arr, val) {
  var high = arr.length - 1;
  var mid = 0;
  var low = 0;
  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] > val) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return low;
}