315. Count of Smaller Numbers After Self

2020-06-11

原题：315. Count of Smaller Numbers After Self

source code

这道题的二分查找插入代码非常模板，可以背下来。

// Runtime: 144 ms, faster than 54.18% of JavaScript online submissions for Count of Smaller Numbers After Self.
// Memory Usage: 39.3 MB, less than 30.13% of JavaScript online submissions for Count of Smaller Numbers After Self.
var countSmaller = function (nums) {
  const arr = [];
  const findInsertIndex = function (num) {
    //二分插入，返回插入的index
    if (!arr.length) {
      return 0;
    }
    let left = 0;
    let right = arr.length - 1;
    while (left + 1 < right) {
      //注意这里
      let mid = left + ~~((right - left) / 2);
      if (arr[mid] >= num) {
        right = mid;
      } else {
        left = mid;
      }
    }
    if (num > arr[right]) {
      //最右
      return right + 1;
    } else if (num <= arr[left]) {
      //最左
      return left;
    } else {
      //中间
      return right;
    }
  };

  const result = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    result[i] = findInsertIndex(nums[i]);
    arr.splice(result[i], 0, nums[i]);
  }

  return result;
};

test cases

test("test1", () => {
  expect(countSmaller([5, 2, 6, 1])).toEqual([2, 1, 1, 0]);
});

test("test2", () => {
  expect(countSmaller([1, 1, 1, 1])).toEqual([0, 0, 0, 0]);
});

test("test3", () => {
  expect(countSmaller([-1, 0])).toEqual([0, 0]);
});

更巧妙的解法

// Runtime: 472 ms, faster than 43.80% of JavaScript online submissions for Count of Smaller Numbers After Self.
// Memory Usage: 40.6 MB, less than 16.35% of JavaScript online submissions for Count of Smaller Numbers After Self.
var countSmaller = function (nums) {
  const arr = [...nums].sort((a, b) => a - b);
  const result = [];
  for (let num of nums) {
    const index = arr.indexOf(num); //因为题目要求的是smaller，因此直接用indexOf（兼容了=的情况），如果要改成largger，用lastIndexOf
    result.push(index);
    arr.splice(index, 1); //这里是这个方法的核心，arr里面剩下的都是还未处理的（right of nums[i]）的元素，并且是升序的
  }

  return result;
};

拓展

实现countLarger：

//方法一
var countLarger = function (nums) {
  const arr = [];
  const findInsertIndex = function (num) {
    //二分插入，返回插入的index
    if (!arr.length) {
      return 0;
    }
    let left = 0;
    let right = arr.length - 1;
    while (left + 1 < right) {
      //注意这里
      let mid = left + ~~((right - left) / 2);
      if (arr[mid] > num) {
        right = mid;
      } else {
        left = mid;
      }
    }
    if (num >= arr[right]) {
      //最右
      return right + 1;
    } else if (num < arr[left]) {
      //最左
      return left;
    } else {
      //中间
      return right;
    }
  };

  const result = [];
  for (let i = nums.length - 1; i >= 0; i--) {
    const index = findInsertIndex(nums[i]);
    result.unshift(result.length - index);
    arr.splice(index, 0, nums[i]);
  }

  return result;
};

//方法二：
var countLarger = function (nums) {
  const arr = [...nums].sort((a, b) => a - b);
  const result = [];
  for (let num of nums) {
    const index = arr.lastIndexOf(num);
    result.push(arr.length - index - 1);
    arr.splice(index, 1);
  }

  return result;
};