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

• -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);
}
}``````

6 个回答

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]
}``````

``````    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++) {
}
// push into the bucket
for (int i = 0; i < arr.length; i++) {
int index = indexFor(arr[i], min, 10);
}
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);
}
}``````

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];
}
}``````

``````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``````

``````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;
}
}``````

###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进