지문은 링크에서 확인해주세요.
본 문제는 해결하지 못했습니다. nums1과 nums2가 각각 1만개 데이터인 테스트 케이스에서 런타임 에러 terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
가 발생하였습니다. 즉, 필자는 제출 환경에서 제한하는 시간 복잡도를 초과하였습니다.
function Heap() {
this.arr = [];
}
Heap.prototype.swap = function (a, b) {
const temp = this.arr[a];
this.arr[a] = this.arr[b];
this.arr[b] = temp;
}
Heap.prototype.getSum = function(i) {
return this.arr[i][0] + this.arr[i][1];
}
Heap.prototype.push = function (e) {
this.arr[this.arr.length] = e;
this.bubbleUp(this.arr.length - 1);
}
Heap.prototype.bubbleUp = function(i) {
const child = i;
const parent = Math.floor((i - 1) / 2);
if(parent >= 0 && this.getSum(child) < this.getSum(parent)) {
this.swap(child, parent);
this.bubbleUp(parent);
}
}
Heap.prototype.pop = function() {
const max = this.arr[0];
this.arr[0] = this.arr[this.arr.length - 1];
this.arr.pop();
this.bubbleDown(0);
return max;
}
Heap.prototype.bubbleDown = function(i) {
let child = 2 * i + 1;
const rightChild = 2 * i + 2;
if(child <= this.arr.length - 1) {
if(
rightChild <= this.arr.length - 1
&& this.getSum(child) > this.getSum(rightChild)
) {
child = rightChild;
}
if(this.getSum(i) > this.getSum(child)) {
this.swap(i, child);
this.bubbleDown(child);
}
}
}
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} k
* @return {number[][]}
*/
var kSmallestPairs = function(nums1, nums2, k) {
const heap = new Heap();
for(const each of nums1) {
for(const other of nums2) {
heap.push([each, other])
}
}
const ans = [];
for(let i = 0; i < k; i++) {
const e = heap.pop();
if(!e) {
continue;
}
ans.push(e);
}
return ans;
};
해답의 전문은 링크를 확인해주세요.
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this._bubbleUp();
}
pop() {
if (this.size() === 1) return this.heap.pop();
const smallest = this.heap[0];
this.heap[0] = this.heap.pop();
this._sinkDown(0);
return smallest;
}
size() {
return this.heap.length;
}
_bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex][0] > this.heap[index][0]) {
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
} else {
break;
}
}
}
_sinkDown(index) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let smallest = index;
if (left < this.size() && this.heap[smallest][0] > this.heap[left][0]) {
smallest = left;
}
if (right < this.size() && this.heap[smallest][0] > this.heap[right][0]) {
smallest = right;
}
if (smallest !== index) {
[this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
this._sinkDown(smallest);
}
}
}
var kSmallestPairs = function(nums1, nums2, k) {
const heap = new MinHeap();
const result = [];
if (nums1.length === 0 || nums2.length === 0) return [];
for (let i = 0; i < Math.min(k, nums1.length); i++) {
heap.push([nums1[i] + nums2[0], i, 0]);
}
while (k > 0 && heap.size() > 0) {
const [val, i, j] = heap.pop();
result.push([nums1[i], nums2[j]]);
k--;
if (j + 1 < nums2.length) {
heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
}
}
return result;
};
본 해답은 힙에 요소를 넣는 행위에서 nums1과 nums2가 정렬된 상태를 활용하였습니다. 따라서, 필자의 해답과 달리 선형 시간을 사용할 수 있습니다.