找出第 n 個最小值

來自 JS101 的練習題，覺得邏輯還蠻神奇的，所以想記下來。

把每一次都當作第一次

其實一般直覺會想到的方法應該是：

1. 把數列排序 => 由小到大
2. 用 n 去從已經排序好的數列裡查值

所以用作弊一點的方法的話會是這樣子：

function findNthMin(arr, n) {
  // 重新排序 => 由小到大
  const sortedArray = arr.sort((a, b) => a-b)
  // array 從 0 開始，所以才要 -1
  return sortedArray[n-1]
}
console.log(findNthMin([1, 2, 3, 4, 5], 2))  // 2
console.log(findNthMin([1, 3, 5, 7, 9], 3))  // 5
console.log(findNthMin([1, 1, 1, 1, 1], 2))  // 1

但這不是這篇文章想介紹的，想介紹的是另外一種思維：

1. 從數列中找出最小值
2. 把最小值從數列中刪除
3. 重複步驟 1、2，直到重複 n 次為止

所以其實每一次都只是在找最小值，但重點在於 每一次都會把最小值移除 這個動作，這個動作會讓你下一次找到的其實是 次小值，接著是 次次小值，以此類推。

所以當你做了 n 次後，那一次的最小值就等同於第 n 個最小值了，挺神奇的吧？馬上來實作看看：

function findNthMin(arr, n) {
  // 儲存第 n 個最小值
  let min = null
  // 重複找最小值 n 次
  for(let i=0; i<n; i++) {
    // 每一次都重新設值為無線大
    min = Infinity
    // 儲存最小值的位置
    let k = null
    // 遍歷陣列，找出最小值
    for(let j=0; j<arr.length; j++) {
      if(arr[j] < min) {
        // 更新最小值
        min = arr[j]
        // 更新最小值的位置
        k = j
      }
    }
    // 刪除最小值
    arr.splice(k, 1)
  }
  // 回傳結果
  return min
}
console.log(findNthMin([1, 2, 3, 4, 5], 2))  // 2
console.log(findNthMin([1, 3, 5, 7, 9], 3))  // 5
console.log(findNthMin([1, 1, 1, 1, 1], 2))  // 1

雖然這解法比較複雜一點，但是還蠻有趣的！

用在排序上

這個方法其實也能用來做排序，參考下面的原始碼：

function sort(arr) {
  // 儲存最小值
  let min = null
  // 儲存排序好的結果
  const result = []
  // 記得儲存陣列長度（因為更新陣列時 length 值會改變）
  // i=0 => arr.length=5
  // i=1 => arr.length=4
  // i=2 => arr.length=3
  // i=3 => arr.length=2 
  // 迴圈就結束了，總共只跑 3 圈，所以只會得到 [1, 2, 3]
  const total = arr.length 
  // 重新排序
  for(let i=0; i<total; i++) {
    // 每一次都重置為無限大
    min = Infinity
    // 儲存最小值的位置
    let k = null
    // 遍歷陣列，找出最小值
    for(let j=0; j<arr.length; j++) {
      if(arr[j] < min) {
        // 更新最小值
        min = arr[j]
        // 更新最小值的位置
        k = j
      }
    }
    // 把最小值放到結果陣列裡
    result[i] = min
    // 移除最小值
    arr.splice(k, 1)
  }
  // 回傳第 n 個最小值
  return result
}
console.log(sort([1, 2, 3, 4, 5]))

就跟原本的做法差不多，但要特別注意 length 值會改變這件事情，不要像我一樣忽略了。