132.最优分组 - 图1

题目概述

题目详情(点我)

给出一个长度为 n 的数组和一个数字 k ，你需要在数组中选出一些数字，这些数字两两之间的差值不能超过k。你需要判断最多能够挑出的数字个数。（n在[1, 100000]之间，k和数组中的数字在[1，1000000000]之间）

输入:
输入数组长度n；选出的两数字最大差值k；和一个长度为n的数组。

输出:
输出最多能够选出的数字个数

题解

解题方法

  • 模拟挪动法

算法知识

  • 尺取法

    • 时间复杂度: n^2
    • 空间复杂度: 1

解题思路

审题

  • int n : 数组内元素个数
  • int k : 最大差值
  • int[] nums : 数组

题目要求

  • 最多选出的数字个数

思路

  • 先对数组进行排序
  • 要想选出的数字最多，就必须保持着最大数字-最小数字的差值为最大差值
  • 如果大于最大差值，则记录下这个当前这个最大值。并舍去最小值, 让第二小的值变成最小值, 再进行比较。 如果还是大于最大差值, 就继续以上步骤。直到当前值的前一个为止。

步骤

  1. 定义变量

    • int temp : 记录当前符合要求的序列的长度, 初始值为1
    • int max : 记录下从遍历开始到结束符合要求的序列的最长长度, 初始值为1
    • int min : 当前序列中的最小值
    • int minI : 最小值对应的数组下标, 初始值为0

  2. 对数组nums进行从小到大排序, 并将最小值nums[0] 赋值给min

  3. 循环遍历数组nums, 并计算符合要求的最长的序列长度

    • 如果 当前值nums[i] - 最小值min 小于最大差值k
      则temp+1

    • 如果 当前值nums[i] - 最小值min 大于 最大差值k

      • 判断temp 与 max的大小, 如果temp 大于max, 则更新max

      • 如果最小值的下标小于当前下标i

        • 则让最小值往前挪一位即 min = nums[++minI],
        • 并且让temp-1 (因为最小值往前挪一位, 序列长度就得-1)
        • 同时i-1 (i-1是为了换一个让新的最小值与当前值比较, 因为for循环中的i会自增)
      • 判断temp是否小于1, 若为1, 则将temp赋值为1. (因为序列最小值就是1)

  4. 循环结束后, 依旧需要让temp和max比较一下。 因为有可能最后一个序列因为最大值与最小值的差值小于最大差值，而没有让temp和max进行比较。

  5. 返回最长序列个数max