一、题干：学生分数的最小差值

难度简单56
给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。

示例 1：
输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法： - [90] 最高分和最低分之间的差值是 90 - 90 = 0 可能的最小差值是 0
示例 2：
输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6 可能的最小差值是 2

提示：

  • 1 <= k <= nums.length <= 1000
  • 0 <= nums[i] <= 105

    二、解题思路：

    1.初版：

  1. 先从小到大排序；

  2. 再滑动窗口，依次比较“相邻的k个数中，最大值-最小值”，最小值即是结果。

    1. func minimumDifference(nums []int, k int) int {
    2.  if k==1||len(nums)==1{
    3.      return 0
    4.  }
    5.  //排序
    6.  for i:=len(nums)-1;i>0;i-- {
    7.      for j:=0;j<i;j++{
    8.          if nums[j]>nums[j+1]{
    9.              temp:=nums[j]
    10.              nums[j]=nums[j+1]
    11.              nums[j+1]=temp
    12.          }
    13.      }
    14.  }
    15.  //滑动窗口
    16.  _min:=int(10e5)
    18.  for i:=0;i<=len(nums)-k;i++{
    19.      if nums[i+k-1]-nums[i]<_min{
    20.          _min=nums[i+k-1]-nums[i]
    21.      }
    22.  }
    24.  return int(_min)
    25. }

    image.png
    好慢。。。。哈哈哈，虽然我很菜，但是这么慢肯定不行的，emmm，好像没有其他途径了，看来只能优化排序了，快排走起～

2. 改进：快排

func minimumDifference(nums []int, k int) int {
    if k==1||len(nums)==1{
        return 0
    }
    //升级排序：快排
    quickSort(nums,0,len(nums)-1)
    //滑动窗口
    _min:=int(10e5)

    for i:=0;i<=len(nums)-k;i++{
        if nums[i+k-1]-nums[i]<_min{
            _min=nums[i+k-1]-nums[i]
        }
    }

    return int(_min)
}
func quickSort(arr []int,l,r int) {
    if r<=l{
        return
    }
    p, q:= partition(arr, l, r)
    quickSort(arr,l,p)
    quickSort(arr,q,r)
}

func partition(arr []int, l, r int) (int,int){
    flag := arr[(l+r)/2]
    p, q := l-1, r+1
    for i := l; i <= r&& i != q;{
        if arr[i]<flag{
            tmp:=arr[p+1]
            arr[p+1]=arr[i]
            arr[i]=tmp
            i++
            p++
        }else if arr[i]==flag{
            i++
        }else {
            tmp:=arr[q-1]
            arr[q-1]=arr[i]
            arr[i]=tmp
            q--
        }
    }
    return p,q
}

看下结果，哈哈哈，看来单单一个排序优化就能提升很多，效果显著，飞起～
image.png