问一道算法题，希望能得到最优解。

Question

对于一个数组，如何找出第 n 小的数字？
例如 [10, 3, 2, 5, 8, 2, 2, 7] 传入 n = 4，则应该返回 3。因为对数组进行非降序 排序(后一个数字大于等于前一个数)结果为 [2, 2, 2, 3, 5, 7, 8, 10]，第 4 个数字（从左到右 从 1 数起）为 3。第 n 小指的就是从小到大排列后的数组下标为 n - 1 的数字。

• -10000 <= array[i] <= 10000
• 0 <= array.length <= 100000
• 1 <= n <= array.length * 数组中的元素可能会出现重复，数组里面的每个数值都大于 JS 整形的数值下界， 小于 JS 整形的数值上界

以下是我的解法:

方法一

    var findNthNumber = function(array,n){
        return array.sort((a,b) => a - b)[n - 1];
    }

方法二:

var findNthNumber = function (array, n) {
        let min = Math.min.apply(null,array);
        let countMin = 0;
        for (let i = 0; i < array.length; i++) {
            if (array[i] === min) {
                countMin++;
                array.splice(i, 1);
                n -= countMin;
            }
        }
        if (n > 0) {
            return findNthNumber(array, n);
        } else {
            return Math.min.apply(null,array);
        }
  }

在不考虑排序的情况下，希望能得到最优解算法。

Answer 1

最优解可以用快速排序的partition思想对数组进行部分排序,时间复杂度O(N)
参考资料:
https://leetcode-cn.com/probl...

function findKthLargest(nums: number[], k: number): number {
  const swap = (i: number, j: number): void => {
    const t = nums[i]
    nums[i] = nums[j]
    nums[j] = t
  }
  const partition = (low: number, hi: number): number => {
    const v = nums[low]

    let i = low
    let j = hi + 1
    while (true) {
      while (nums[++i] < v) if (i >= hi) break

      while (nums[--j] > v) if (j <= low) break

      if (i >= j) break

      swap(i, j)
    }

    swap(low, j)
    return j
  }

  let low = 0
  let hi = nums.length - 1
  let index
  k = nums.length - k

  do {
    index = partition(low, hi)

    if (index > k) {
      hi = index - 1
    } else if (index < k) {
      low = index + 1
    }
  } while (index !== k)

  return nums[index]
}

Answer 2

如果你的数组都是整数，可以选择桶式的排序法，该排序法不太占用CPU，而利用内存实现了很快的排序。
具体可用字典键值表来实现。

以下摘自维基百科

    private int indexFor(int a, int min, int step) {
        return (a - min) / step;
    }

    public void bucketSort(int[] arr) {

        int max = arr[0], min = arr[0];
        for (int a : arr) {
            if (max < a)
                max = a;
            if (min > a)
                min = a;
        }
        // 該值也可根據實際情況選擇
        int bucketNum = max / 10 - min / 10 + 1;
        List buckList = new ArrayList<List<Integer>>();
        // create bucket
        for (int i = 1; i <= bucketNum; i++) {
            buckList.add(new ArrayList<Integer>());
        }
        // push into the bucket
        for (int i = 0; i < arr.length; i++) {
            int index = indexFor(arr[i], min, 10);
            ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
        }
        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>) buckList.get(i);
            insertSort(bucket);
            for (int k : bucket) {
                arr[index++] = k;
            }
        }

    }

    // 把桶內元素插入排序
    private void insertSort(List<Integer> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

Answer 3

典型的TopK问题，搜一下就有了

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入

Answer 4

我不知道是不是最优解，思路

1. 定义一个缓存（数组），其大小不大于 n，内部按从大到小的顺序排列。
2. 遍历源数组，将每一个元素放进缓存，但是
3. 放的时候要按顺序找到它该插入的位置，而且
4. 如果放入后缓存长度大于，就把头上的那个（最大的）扔掉，
5. 遍历完成后，缓存头上那个就是要找的值

先定义缓存类（含操作）

class FixedSizeBuffer {
    /**
     * 
     * @param {number} maxLength 
     * @param {function} findIndex 查找某个值该放入的位置，它也能决定数组的顺序
     */
    constructor(maxLength, findIndex) {
        this.maxLength = maxLength;
        this.data = [];
        this.findIndex = findIndex;
    }

    /**
     * 放入一个数，给它放在正确的位置上去
     * @param {number} n 
     */
    push(n) {
        const index = this.findIndex(this.data, n);
        if (index < 0) {
            this.data.push(n);
        } else {
            this.data.splice(index, 0, n);
        }
        if (this.data.length > this.maxLength) {
            this.data.shift();
        }
    }

    get max() {
        return this.data[0];
    }
}

然后就是查找过程，这里直接用的 Array.prototype.findIndex 来查找位置，如果换作二分查找，对于数据量大的情况会快得多。

function findNthLess(list, n) {
    const buffer = new FixedSizeBuffer(
        n,
        (list, v) => {
            return list.findIndex(n => n < v);
        }
    );

    list.forEach(v => buffer.push(v));
    return buffer.max;
}

应用（测试）

console.log(findNthLess2([10, 3, 2, 5, 8, 2, 2, 7], 4));  // 3
console.log(findNthLess2([10, 3, 2, 5, 8, 2, 2, 7], 5));  // 5
console.log(findNthLess2([10, 3, 2, 5, 8, 2, 2, 7], 6));  // 7

---

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。

Answer 5

这不是最大堆嘛，构建K大小的最大堆，小于堆顶就更新堆。

Answer 6

我将我的方法二做了优化，如下:

var findNthNumber = function (array, n) {
    let min = Math.min.apply(null, array);
    array.splice(array.indexOf(min), 1);
    n--;
    if (n > 0) {
      return findNthNumber(array, n);
    } else {
      return min;
    }
  }

时间复杂度为O(n),个人感觉我这个优化好像还不错。