https://leetcode.com/problems/kth-largest-element-in-an-array/description
배열이 [8, 6, 12, 9, 3, 4]이고 k가 2인 경우 이 배열에서 두 번째로 큰 요소를 찾아야 합니다. 먼저 배열을 정렬합니다: [3, 4, 6, 8, 9, 12] 두 번째로 큰 요소이므로 출력은 9가 됩니다.
var findKthLargest = function(nums, k) { // Sort the array in ascending order nums.sort((a, b) => a - b); // Return the kth largest element return nums[nums.length - k]; };
그러므로 전체 시간 복잡도는 O(n log n)입니다.
var findKthLargest = function(nums, k) { // Create a min-heap using a priority queue let minHeap = new MinPriorityQueue(); // Add the first k elements to the heap for (let i = 0; i < k; i++) { //minHeap.enqueue(nums[i]): Adds the element nums[i] to the min-heap. minHeap.enqueue(nums[i]); } // Iterate through the remaining elements for (let i = k; i < nums.length; i++) { //minHeap.front().element: Retrieves the smallest element in the min-heap without removing it. if (minHeap.front().element < nums[i]) { // minHeap.dequeue(): Removes the smallest element from the min-heap. minHeap.dequeue(); // Add the current element minHeap.enqueue(nums[i]); } } // The root of the heap is the kth largest element return minHeap.front().element; };
현재 요소 = 3
현재 요소 = 5
현재 요소 = 4
참고: Leetcode가 빠른 선택을 제한하더라도 이 접근 방식은 대부분의 테스트 사례를 통과하므로 기억해야 합니다
//Quick Select Algo function quickSelect(list, left, right, k) if left = right return list[left] Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1
var findKthLargest = function(nums, k) { // Call the quickSelect function to find the kth largest element return quickSelect(nums, 0, nums.length - 1, nums.length - k); }; function quickSelect(nums, low, high, index) { // If the low and high pointers are the same, return the element at low if (low === high) return nums[low]; // Partition the array and get the pivot index let pivotIndex = partition(nums, low, high); // If the pivot index is the target index, return the element at pivot index if (pivotIndex === index) { return nums[pivotIndex]; } else if (pivotIndex > index) { // If the pivot index is greater than the target index, search in the left partition return quickSelect(nums, low, pivotIndex - 1, index); } else { // If the pivot index is less than the target index, search in the right partition return quickSelect(nums, pivotIndex + 1, high, index); } } function partition(nums, low, high) { // Choose the pivot element let pivot = nums[high]; let pointer = low; // Rearrange the elements based on the pivot for (let i = low; i < high; i++) { if (nums[i] <= pivot) { [nums[i], nums[pointer]] = [nums[pointer], nums[i]]; pointer++; } } // Place the pivot element in its correct position [nums[pointer], nums[high]] = [nums[high], nums[pointer]]; return pointer; }
위 내용은 배열에서 K번째로 큰 요소의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!