专栏首页前端小书童一天一大 leet(计算右侧小于当前元素的个数)难度:困难-Day20200711

一天一大 leet(计算右侧小于当前元素的个数)难度:困难-Day20200711

题目:

给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质:counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例

输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

抛砖引玉

暴力循环

  • 声明一个存储结果的数组填充默认值 0
  • 逆向遍历输入数字
  • 对每个数组指定循环之后的数统计比其小的数字个数存储到存储结果的数组中
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function (nums) {
  let len = nums.length,
    _result = Array(len).fill(0)
  for (let i = len - 1; i >= 0; i--) {
    _result[i] = get_num(i, nums, nums[i])
  }
  function get_num(start, nums, n) {
    let num = 0
    if (start === nums.length - 1) return num
    for (let i = start; i <= nums.length - 1; i++) {
      if (nums[i] < n) num++
    }
    return num
  }
  return _result
}

不是吧?这样一道困难的题就完了?没那么简单,优化下吧

二分法查找

思路

上面的循环会发现i越小循环的次数越多,而且对右边一个数的比较越多 最后一位数需要参与len-1次比较

  • 如果能记录每一个位置的依次小于它的数,循环时我们只要知道新加入在哪两个数之间就可以之间得到它的结果
  • 查询一个数在哪两个数之间就演化成了排序的问题
  • 在一个数组里面最快定位一个数的位置,最快为:数组有序,二分法 则,逻辑就变成了:从nums从右向左取出元素到新数组排序,并且记录每一个数的位置

实现

  • 依次取出nums到一个新数字
  • 新数组为排序数组
  • 设取到nums[i],项新数组中插入时需要知道插入位置,插入位置即要求的右侧小于它的数
  • 插入时数据越多循环查询位置的次数越多,优化循环,借助二分法的思路求要插入的数据在新数组中的插入位置
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function (nums) {
  let len = nums.length
  if (len == 0) return nums
  let _result = Array(len).fill(0),
    dp = [];
  for (let i = len - 1; i >= 0; i--) {
    // 计算位置
    let index = findIndex(dp, nums[i])
    // 插入数据
    dp.splice(index, 0, nums[i])
    // 记录索引
    _result[i] = index
  }
  function findIndex(arr, target) {
    let start = 0,
        end = arr.length - 1;
    while (start < end) {
      let mid = parseInt((start + end) / 2,10)
      if (arr[mid] < target) {
        start = mid + 1;
      } else {
        end = mid;
      }
    }
    if (arr[start] < target) return start + 1;
    return start
  }
  return _result
}

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:坑人的小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】下一个排列 (难度:中等) - Day20201110

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

    前端小书童
  • 【一天一大 lee】有多少小于当前数字的数字 (难度:简单) - Day20201026

    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

    前端小书童
  • 【一天一大 lee】存在重复元素 (难度:简单) - Day20201213

    如果任意一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false 。

    前端小书童
  • 【一天一大 lee】下一个排列 (难度:中等) - Day20201110

    实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

    前端小书童
  • MaxSubarray最大子序和问题

    回顾leetcode原来做过的题,看到了经典的最大子序和问题,收藏了一个好回答。 这个问题是这样的(https://leetcode.com/problems...

    生信编程日常
  • 画解算法:219. 存在重复元素 II

    https://leetcode-cn.com/problems/contains-duplicate-ii/

    灵魂画师牧码
  • 【每日算法Day 75】字节跳动面试题:手撕困难题,看过我Day 71的人都会做了!

    韦阳的博客:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法[2]

    godweiyang
  • 1.比较排序之冒泡排序

      冒泡排序可以说是在排序算法中最为入门级别的算法之一了。因为其简单易于理解,常在课堂中作为排序的入门算法。   冒泡排序见名生意,其排序过程如同水里的泡一般由...

    用户1148394
  • leetcode每日一题:283. 移动零

    地址:https://leetcode-cn.com/problems/move-zeroes/

    用户3578099
  • 漫画:经典鹅厂面试题(2Sum,3Sum,4Sum)

    该题为 二数之和 的进阶版本,当然还有一个进阶版本为 四数之和。我们将会一一进行分析!

    程序员小浩

扫码关注云+社区

领取腾讯云代金券