题目地址：学生分数的最小差值

解题思路

看到题目，最先想到是将数组排序好，这样的话，在计算差值的时候，就直接是当前的下标i是最小值,当前范围内的最大的值就是i+k-1，例如：【9，4，1，7】，k = 3，如图：

image.png
排序好后，将nums[i+k-1] - nums[i]的差值放到数组里，在进行排序的操作，最后返回排好序后的数组中的第一个元素

代码

  1. const sort = (nums,len)=>{
  2.    for(let i = 0;i<len;i++){
  3.        let minId = i;
  4.        for(let j = i+1;j<len;j++){
  5.         if(nums[minId]>nums[j]){
  6.           minId = j
  7.         }
  8.        } 
  9.        [nums[i],nums[minId]] = [nums[minId],nums[i]]
  10.    }
  11.    return nums;
  12. }
  13.  var minimumDifference = function(nums, k) {
  14.      if(k === 1) return 0;
  15.      nums.sort((a, b) => a - b );
  16.     const len = nums.length;
  17.      if(k>=1 && k<=nums.length && nums.length<=1000){
  18.         const len = nums.length;
  19.         const arr = sort(nums,len);
  20.         const temp = [];
  21.         for(let i = 0;i<len;i++){
  22.             for(let j = i+k-1;j<len;j++){
  23.                 temp.push(Math.abs(arr[j]-arr[i]));
  24.             }
  25.         }
  26.         const result = sort(temp,temp.length);
  27.         return result[0]
  28.      }else{
  29.          return 0;
  30.      }
  31. };
  33. const nums = [9,4,7,1];
  34. const k = 2;
  36. console.log('--原始版本--',minimumDifference(nums,k));

订正

提交代码后，发现如果数据量大时，不能通过，因此看了题解，订正了新版本

  1. const minimumDifference2 = (nums,k)=> {
  2.     // 首先进行排序的操作
  3.     if(k === 1) return 0;
  4.     const len = nums.length;
  5.     nums.sort((a,b)=> a - b);
  6.     // 对排序的数据进行操作
  7.     // 代表number最大的安全整数
  8.     let abs = Number.MAX_SAFE_INTEGER;
  9.     for(let i = 0;i+k-1<len;i++){
  10.         abs = Math.min(abs,nums[i+k-1]-nums[i])
  11.     }
  12.     return abs;
  13. }
  16. console.log('--dd',minimumDifference2(nums,k));

优化的点：

  • 排序这块，我之前使用的是选择排序，优化后直接使用了Array.sort()的原生的方法，简化了代码量
  • 在计算差值这块，利用的滑动窗口的概念，其实和订正前的版本有点类似，只不过在i的取值范围那块做了变更
  • 最可取的是，在计算最小值时，直接采用了Math.min来计算差值，省去了再次排序所涉及到的时间、空间复杂度的计算

总结

  • Array.sort()
  • Math.min()
  • 滑动窗口的概念