# 215.kth-largest-element-in-an-array

**Published by:** [guanbinrui.eth](https://paragraph.com/@guanbinrui/)
**Published on:** 2022-03-21
**URL:** https://paragraph.com/@guanbinrui/215-kth-largest-element-in-an-array

## Content

/* * @lc app=leetcode id=215 lang=javascript * * [215] Kth Largest Element in an Array */ // @lc code=start //#region Heap (function() { var Heap, defaultCmp, floor, heapify, heappop, heappush, heappushpop, heapreplace, insort, min, nlargest, nsmallest, updateItem, _siftdown, _siftup; (floor = Math.floor), (min = Math.min); /* Default comparison function to be used */ defaultCmp = function(x, y) { if (x < y) { return -1; } if (x > y) { return 1; } return 0; }; /* Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default a.length) bound the slice of a to be searched. */ insort = function(a, x, lo, hi, cmp) { var mid; if (lo == null) { lo = 0; } if (cmp == null) { cmp = defaultCmp; } if (lo < 0) { throw new Error('lo must be non-negative'); } if (hi == null) { hi = a.length; } while (lo < hi) { mid = floor((lo + hi) / 2); if (cmp(x, a[mid]) < 0) { hi = mid; } else { lo = mid + 1; } } return [].splice.apply(a, [lo, lo - lo].concat(x)), x; }; /* Push item onto heap, maintaining the heap invariant. */ heappush = function(array, item, cmp) { if (cmp == null) { cmp = defaultCmp; } array.push(item); return _siftdown(array, 0, array.length - 1, cmp); }; /* Pop the smallest item off the heap, maintaining the heap invariant. */ heappop = function(array, cmp) { var lastelt, returnitem; if (cmp == null) { cmp = defaultCmp; } lastelt = array.pop(); if (array.length) { returnitem = array[0]; array[0] = lastelt; _siftup(array, 0, cmp); } else { returnitem = lastelt; } return returnitem; }; /* Pop and return the current smallest value, and add the new item. This is more efficient than heappop() followed by heappush(), and can be more appropriate when using a fixed size heap. Note that the value returned may be larger than item! That constrains reasonable use of this routine unless written as part of a conditional replacement: if item > array[0] item = heapreplace(array, item) */ heapreplace = function(array, item, cmp) { var returnitem; if (cmp == null) { cmp = defaultCmp; } returnitem = array[0]; array[0] = item; _siftup(array, 0, cmp); return returnitem; }; /* Fast version of a heappush followed by a heappop. */ heappushpop = function(array, item, cmp) { var _ref; if (cmp == null) { cmp = defaultCmp; } if (array.length && cmp(array[0], item) < 0) { (_ref = [array[0], item]), (item = _ref[0]), (array[0] = _ref[1]); _siftup(array, 0, cmp); } return item; }; /* Transform list into a heap, in-place, in O(array.length) time. */ heapify = function(array, cmp) { var i, _i, _j, _len, _ref, _ref1, _results, _results1; if (cmp == null) { cmp = defaultCmp; } _ref1 = function() { _results1 = []; for ( var _j = 0, _ref = floor(array.length / 2); 0 <= _ref ? _j < _ref : _j > _ref; 0 <= _ref ? _j++ : _j-- ) { _results1.push(_j); } return _results1; } .apply(this) .reverse(); _results = []; for (_i = 0, _len = _ref1.length; _i < _len; _i++) { i = _ref1[_i]; _results.push(_siftup(array, i, cmp)); } return _results; }; /* Update the position of the given item in the heap. This function should be called every time the item is being modified. */ updateItem = function(array, item, cmp) { var pos; if (cmp == null) { cmp = defaultCmp; } pos = array.indexOf(item); if (pos === -1) { return; } _siftdown(array, 0, pos, cmp); return _siftup(array, pos, cmp); }; /* Find the n largest elements in a dataset. */ nlargest = function(array, n, cmp) { var elem, result, _i, _len, _ref; if (cmp == null) { cmp = defaultCmp; } result = array.slice(0, n); if (!result.length) { return result; } heapify(result, cmp); _ref = array.slice(n); for (_i = 0, _len = _ref.length; _i < _len; _i++) { elem = _ref[_i]; heappushpop(result, elem, cmp); } return result.sort(cmp).reverse(); }; /* Find the n smallest elements in a dataset. */ nsmallest = function(array, n, cmp) { var elem, i, los, result, _i, _j, _len, _ref, _ref1, _results; if (cmp == null) { cmp = defaultCmp; } if (n * 10 <= array.length) { result = array.slice(0, n).sort(cmp); if (!result.length) { return result; } los = result[result.length - 1]; _ref = array.slice(n); for (_i = 0, _len = _ref.length; _i < _len; _i++) { elem = _ref[_i]; if (cmp(elem, los) < 0) { insort(result, elem, 0, null, cmp); result.pop(); los = result[result.length - 1]; } } return result; } heapify(array, cmp); _results = []; for ( i = _j = 0, _ref1 = min(n, array.length); 0 <= _ref1 ? _j < _ref1 : _j > _ref1; i = 0 <= _ref1 ? ++_j : --_j ) { _results.push(heappop(array, cmp)); } return _results; }; _siftdown = function(array, startpos, pos, cmp) { var newitem, parent, parentpos; if (cmp == null) { cmp = defaultCmp; } newitem = array[pos]; while (pos > startpos) { parentpos = (pos - 1) >> 1; parent = array[parentpos]; if (cmp(newitem, parent) < 0) { array[pos] = parent; pos = parentpos; continue; } break; } return (array[pos] = newitem); }; _siftup = function(array, pos, cmp) { var childpos, endpos, newitem, rightpos, startpos; if (cmp == null) { cmp = defaultCmp; } endpos = array.length; startpos = pos; newitem = array[pos]; childpos = 2 * pos + 1; while (childpos < endpos) { rightpos = childpos + 1; if (rightpos < endpos && !(cmp(array[childpos], array[rightpos]) < 0)) { childpos = rightpos; } array[pos] = array[childpos]; pos = childpos; childpos = 2 * pos + 1; } array[pos] = newitem; return _siftdown(array, startpos, pos, cmp); }; Heap = (function() { Heap.push = heappush; Heap.pop = heappop; Heap.replace = heapreplace; Heap.pushpop = heappushpop; Heap.heapify = heapify; Heap.updateItem = updateItem; Heap.nlargest = nlargest; Heap.nsmallest = nsmallest; function Heap(cmp) { this.cmp = cmp != null ? cmp : defaultCmp; this.nodes = []; } Heap.prototype.push = function(x) { return heappush(this.nodes, x, this.cmp); }; Heap.prototype.pop = function() { return heappop(this.nodes, this.cmp); }; Heap.prototype.peek = function() { return this.nodes[0]; }; Heap.prototype.contains = function(x) { return this.nodes.indexOf(x) !== -1; }; Heap.prototype.replace = function(x) { return heapreplace(this.nodes, x, this.cmp); }; Heap.prototype.pushpop = function(x) { return heappushpop(this.nodes, x, this.cmp); }; Heap.prototype.heapify = function() { return heapify(this.nodes, this.cmp); }; Heap.prototype.updateItem = function(x) { return updateItem(this.nodes, x, this.cmp); }; Heap.prototype.clear = function() { return (this.nodes = []); }; Heap.prototype.empty = function() { return this.nodes.length === 0; }; Heap.prototype.size = function() { return this.nodes.length; }; Heap.prototype.clone = function() { var heap; heap = new Heap(); heap.nodes = this.nodes.slice(0); return heap; }; Heap.prototype.toArray = function() { return this.nodes.slice(0); }; Heap.prototype.insert = Heap.prototype.push; Heap.prototype.top = Heap.prototype.peek; Heap.prototype.front = Heap.prototype.peek; Heap.prototype.has = Heap.prototype.contains; Heap.prototype.copy = Heap.prototype.clone; return Heap; })(); // export Heap to current context this.Heap = Heap; }.call(global)); //#endregion /** * @param {number[]} nums * @param {number} k * @return {number} */ var findKthLargest = function(nums, k) { const maxHeap = new Heap((x, y) => y - x); for (const num of nums) { maxHeap.push(num); } for (let i = 0; i < k - 1; i += 1) { maxHeap.pop(); } return maxHeap.pop(); }; /** * @param {number[]} nums * @param {number} k * @return {number} */ var findKthLargest = function(nums, k) { const minHeap = new Heap(); for (const num of nums) { minHeap.push(num); // only maintains a k size heap if (minHeap.size() > k) { minHeap.pop(); } } return minHeap.top(); }; /** * Quick Sort * @param {number[]} nums * @param {number} k * @return {number} */ var findKthLargest = function(nums, k) { function swap(l, r) { const temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; } function mid(l, r, m) { const _l = nums[l]; const _r = nums[r]; const _m = nums[m]; if ((_l < _r || _l < _m) && (_l > _r || _l > _m)) { return l; } if ((_r < _l || _r < _m) && (_r > _l || _r > _m)) { return r; } return m; } function partition(l, r, m) { if (l === r) return l; const p = mid(l, r, m); // swap p to last if (p !== r) { swap(p, r); } let _l = l; let _r = r - 1; while (_l < _r) { while (nums[_l] < nums[r]) _l++; while (nums[_r] > nums[r]) _r--; if (_l < _r) { swap(_l, _r); _l++; _r--; } } // swap p back if (nums[_l] <= nums[r]) { swap(_l + 1, r); return _l + 1; } swap(_l, r); return _l; } function find(l, r) { const m = Math.floor((l + r) / 2); const p = partition(l, r, m); // povit index const t = nums.length - k; // target index if (p === t) { return nums[p]; } if (p < t) { return find(p + 1, r); } return find(l, p - 1); } return find(0, nums.length - 1); }; // @lc code=end

## Publication Information

- [guanbinrui.eth](https://paragraph.com/@guanbinrui/): Publication homepage
- [All Posts](https://paragraph.com/@guanbinrui/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@guanbinrui): Subscribe to updates