阅读 54

leetcode703 javascript

题目

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

解法

维护K个有序数组

优点:直观

维护长度为K的最小堆

优点:时间复杂度较低
缺点:如果语言本身没有实现优先队列,则需要自己实现,代码较复杂。

待优化的代码

var KthLargest = function(k, nums) {
  this.k = k
  this.minHeap = new Array(k)

  this.updateHeap = () => {
    let minNum = this.minHeap[0]
    let minIndex = 0
    for(let i = 1; i < this.minHeap.length; i ++) {
      if(minNum >= this.minHeap[i]) {
        minNum = this.minHeap[i]
        minIndex = i
      }
    }
    this.minHeap.push(minNum)
    this.minHeap.splice(minIndex, 1)
  }
  if(nums.length >= k) {
    this.minHeap = nums.filter((value, index) => index < k).map(value => value)
    this.updateHeap()
    // console.log(this.minHeap)
    for(let i = k; i < nums.length; i ++) {
      if(this.minHeap[this.minHeap.length - 1] <= nums[i]) {
        this.minHeap[this.minHeap.length - 1] = nums[i]
      }
      this.updateHeap()
    }
  } else {
    this.minHeap = nums.map((value, index) => {
      return nums[index]
    })
    this.updateHeap()
  }
  console.log(this.minHeap)
};


/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
  if(this.minHeap.length < this.k) {
    this.minHeap.push(val)
    this.updateHeap()
  } else if(this.minHeap[this.minHeap.length - 1] < val) {
    this.minHeap[this.minHeap.length - 1] = val
    this.updateHeap()
  }
  console.log(this.minHeap[this.minHeap.length - 1], 'add', val, 
  // this.minHeap
  )
  return this.minHeap[this.minHeap.length - 1]
};
复制代码


更新一波

今天不做新题,打算把昨天的解题优化一下,首先能想到的就是更新堆的循环改成while循环,两个指针同时从左右开始循环,这样平均情况下直接就可以减少n/2的时间复杂度。
于是乎,开始改进,放上去代码,结果大跌眼镜,结果并没有快很多,好像差不多?!

    let left_i = 0
    let right_i = this.minHeap.length
    while (left_i <= right_i) {
      if(minNum >= this.minHeap[left_i]) {
        minNum = this.minHeap[left_i]
        minIndex = left_i
      }
      if(minNum >= this.minHeap[right_i]) {
        minNum = this.minHeap[right_i]
        minIndex = right_i
      }
      left_i ++
      right_i --
    }
复制代码

左思右想,耐不住,直接去看执行最快的范例代码,人家是这么写的

var heapify = function (arr, i) {
    let len = arr.length,
        left = 2 * i,
        right = 2 * i + 1,
        minimum = i;

    if (left < len && arr[left] < arr[minimum]) minimum = left;
    if (right < len && arr[right] < arr[minimum]) minimum = right;

    if (minimum !== i) {
        const tmp = arr[i];
        arr[i] = arr[minimum];
        arr[minimum] = tmp;
        heapify(arr, minimum);
    }
}

var buildMinHeap = function (arr) {
    const len = arr.length;
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        heapify(arr, i);
    }
}


/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function (k, nums) {
    let i = 0, len = nums.length;
    this.k = k;
    this.nums = [];
    for (i = 0; i < k && i < len; i++) {
        this.nums[i] = nums[i];
    }
    buildMinHeap(this.nums);
    for (; i < len; i++) {
        const num = nums[i];
        if (this.nums[0] < num) {
            this.nums[0] = num;
            heapify(this.nums, 0);
        }
    }
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
    const k = this.k;
    if (this.nums.length === k) {
        if (this.nums[0] < val) {
            this.nums[0] = val;
            heapify(this.nums, 0);
        }
    } else {
        this.nums.push(val);
        buildMinHeap(this.nums);
    }
    return this.nums[0];
};
复制代码

写了个更新最小堆和搭建最小堆的方法,代码非常简洁,其中一句代码看着非常舒服for (i = 0; i < k && i < len; i++) {这个for循环中间的条件,原来条件还可以这么玩儿,涨姿势了。


加油,每天学习一点点。

关注下面的标签,发现更多相似文章
评论