215.数组中的第k个最大元素

/*
 * @lc app=leetcode.cn id=215 lang=typescript
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
function findKthLargest(nums: number[], k: number): number {
	// return bubblingSort(nums)[nums.length - k];
	return sortArray(nums)[nums.length - k];
}

/* 归并排序：通过 */
function sortArray(nums: number[]): number[] {
	if (nums.length <= 1) return nums;
	const m = Math.floor(nums.length / 2);
	const l = nums.slice(0, m);
	const r = nums.slice(m);
	return merge(sortArray(l), sortArray(r));
}

function merge(left: number[], right: number[]) {
	let result: number[] = [];
	let leftIndex = 0;
	let rightIndex = 0;

	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex++;
		} else {
			result.push(right[rightIndex]);
			rightIndex++;
		}
	}
	return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}


// 冒泡排序：超时
// function bubblingSort(nums: number[]): number[] {
// 	let r = nums.length - 1;
// 	for (let i = 0; i < nums.length; i++) {
// 		for (let j = 0; j < r; j++) {
// 			if (nums[j] > nums[j + 1]) {
// 				[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
// 			}
// 		}
// 		r--;
// 	}
// 	return nums;
// }


console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));
// @lc code=end