实现函数solution(arr, k)

[Sunny-117]

No description provided.

[Sunny-117]

// arr是number数组，k是number，返回前k个最小的数字组成的数组，保持相对顺序
// 输入:[1,2,3,4,5,3,2]，3，输出：[1,2,2]
// 输入:[1,2,3,4,5,3,2]，4，输出：[1,2,3,2]
// 输入:[1,2,3,4,5,3,2]，5，输出：[1,2,3,3,2]

[bearki99]

function Solution(arr, k){
    const h = [0];
    let size = arr.length;
    let res = [];
    for(let i = 0; i < arr.length ; i++){
        h.push({
            value: arr[i],
            index: i
        })
    }
    function up(u){
        let t = u;
        if(u*2 <= size && h[u*2].value < h[t].value) t = u * 2;
        if(u * 2 + 1 <= size && h[u*2+1].value < h[t].value) t = u * 2 + 1;
        if(u !== t){
            [h[u], h[t]] = [h[t], h[u]];
            up(t);
        }
    }
    for(let i = Math.floor(size / 2); i; i--) up(i);
    while(k--){
        res.push(h[1]);
        h[1] = h[size];
        size--;
        up(1);
    }
    res.sort((a, b)=>a.index - b.index);
    res = res.map((item)=>item.value);
    return res;
}

const arr = [1,2,3,4,5,3,2];
console.log(Solution(arr, 4));

相较于传统的堆排序，还需要一个index去记录元素的位置

[ZCoward]

function solution(arr, k) {
const map = new Map();
// 键为原数组的索引，值为对应元素
arr.forEach((i, index) => {
map.set(index, i)
});
// 将map转化为数组，[[index,item],[index,item]...]
// 先每一项里面的元素大小排序 a[1] - b[1] ，根据k截取数组，再根据每一项里的索引值恢复原序 a[0] - b[0]
let res = Array.from(map).sort((a, b) => a[1] - b[1]).slice(0, k).sort((a, b) => a[0] - b[0]);
let result = [];
// 按顺序推入即可
res.forEach(i=>{
result.push(i[1])
})
return result;
}
console.log(solution([1,2,3,4,5,3,2],4)) //[1, 2, 3, 2]
//console.log(solution([1,2,3,4,5,3,2],3)) //[1, 2, 2]

[QdabuliuQ]

     class Heap {
      constructor(arr, compare) {
        this.arr = arr
        this.compare = compare
        this.heapify()
      }
      get size() {
        return this.arr.length
      }
      swap(i, j) {
        [this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]]
      }
      heapify() {
        if(this.size <= 1) return
        for(let i = 1; i < this.size; i ++) {
          this.bubbleUp(i)
        }
      }
      pop() {
        if(this.size === 0) return null
        if(this.size === 1) return this.arr.pop()
        const res = this.arr[0]
        this.arr[0] = this.arr.pop()
        this.bubbleDown(0)
        return res
      }
      push(val) {
        this.arr.push(val)
        this.bubbleUp(this.size-1)
      }
      bubbleUp(idx) {
        while(idx) {
          let pIdx = Math.floor((idx-1)/2)
          if(this.compare(this.arr[idx], this.arr[pIdx])) {
            this.swap(idx, pIdx)
            idx = pIdx
          } else break
        }
        console.log(this.arr);
      }
      bubbleDown(idx) {
        while(idx < this.size) {
          let fIdx = idx
          let lIdx = idx*2+1, rIdx = idx*2+2
          if(lIdx < this.size && this.compare(this.arr[lIdx], this.arr[fIdx])) {
            fIdx = lIdx
          }
          if(rIdx < this.size && this.compare(this.arr[rIdx], this.arr[fIdx])) {
            fIdx = rIdx
          }
          if(fIdx != idx) {
            this.swap(idx, fIdx)
            idx = fIdx
          } else break
        }
      }
    }

    function getVal(arr = [], cnt = 0) {
      if(arr.length === 0 || cnt === 0) return []
      let heap = new Heap([...arr], (a,b) => a<b)
      let res = []
      while(res.length < cnt) {
        let val = heap.pop()
        res.push(val)
      }
      return res
    }

[kangkang123269]

function smallestK(arr, k) {
  // 将数组中每个元素和其索引打包在一起
  let indexedArr = arr.map((value, index) => ({value, index}));

  // 按照元素值大小排序，如果值相同则按照索引排序
  indexedArr.sort((a, b) => {
    if (a.value !== b.value) {
      return a.value - b.value;
    } else {
      return a.index - b.index;
    }
  });

  // 取出前k个元素，并且只保留值部分
  let result = indexedArr.slice(0, k).map(item => item.value);

  return result;
}

console.log(smallestK([1,2,3,4,5,3,2],3)); // 输出：[1 ,2 ,2]
console.log(smallestK([1 ,2 ,3 ,4 ,5 ,3 ,2]，4)); // 输出：[1 ，2 ，2 ，3]
console.log(smallestK([1 ,2 ,3 ,4 ,5 ，3 ，2]，5)); // 输出：[1 ，2 ，2 ，3 ，3]

[gswysy]

思路简单，但空间复杂度较大

function solution(arr, k) {
    return arr.map((item, index) => {
        return {
            v: item,
            i: index
        }
    }).sort((a, b) => {
        return a.v - b.v
    }).slice(0, k).sort((a, b) => {
        return a.i - b.i
    }).map(item => item.v)
}