215. Kth Largest Element in an Array

문제링크: https://leetcode.com/problems/kth-largest-element-in-an-array/

O(n)의 시간복잡도로 배열의 n번째 큰 수를 구하는 문제다.

Solution

Quick Selection

처음엔 heap을 이용한 알고리즘을 구상했는데, 요구 조건에서 0(n)의 시간 복잡도를 요구해 O(nlogn)의 힙을 이용한 알고리즘은 불가능했다. 문제를 나눠 해결하는 퀵소트의 알고리즘과 비슷한 원리를 이용해 O(n)의 시간복잡도를 가진 Quick selection 알고리즘을 찾을 수 있었다. 문제의 크기가 평균적으로 반으로 줄어들며 n + 1/2n + 1/4n + 1/8n + ... = 2n의 O(n)의 시간복잡도를 가진 퀵선택 알고리즘을 통해 해결해보았다.

Algorithm

먼저 기존의 퀵소트의 파티션분할 알고리즘을 구현하기 위해 영상을 참고했다.
퀵소트 파티션: https://www.youtube.com/watch?v=MZaf_9IZCrc

• 여기서 i는 피벗보다 작은 수의 끝 기준점이되고 j를 증가시키면서 탐색한다.
• j를 통해 피벗보다 큰 수를 만났을 때는 그대로 지나간다.
• j가 피벗보다 작은 수를 만났을 때는 i에는 작은 수가 들어있고 i + 1에는 큰 수가 들어있기 때문에 ++i를 한 후 j의 값과 바꾼다. (i++을 통해 작은수 끝 기준점을 키우고 그곳에 j위치에 있는 작은수를 넣는 것이다.)
• 이를 피벗 바로 전까지 반복하고 피벗과 큰 수중 가장 앞을 바꿔 가운데로 삽입한다.

// 피벗을 기준으로 좌우로 분할
    const partition = (left, right) => {
      const pivot = nums[right];
      let i = left - 1;
      for (let j = left; j < right; j++) {
        if (nums[j] >= pivot) continue;
        if (nums[j] < pivot) {
          swap(++i, j);
        }
      }
      swap(++i, right); // Pivot to middle
      return i; // Pivot idx
    }
    
    const swap = (l, r) => {
      [nums[l], nums[r]] = [nums[r], nums[l]];
    }

이 파티션 함수를 통해 피벗을 기준으로 좌우로 나누고 피벗의 인덱스(i)를 반환한다.

• quickSelect는 left와 right의 범위 내에서 k번째로 큰 수를 찾는 함수다.
• 먼저 partition을 통해 피벗을 기준으로 좌와 우를 나눈다.
• nums.length - pivotIdx는 현재 피벗이 몇번째로 큰 수 인지 나타낸다.
• 위 값이 k 보다 작은 경우 피벗보다 더 작은 부분을 탐색, 큰 경우 더 큰부분을 탐색한다.
• 위 과정 중 nums.length - pivotIdx와 k의 위치가 일치하면 피벗을 반환한다.

var findKthLargest = function(nums, k) { 
  // 피벗을 기준으로 좌우로 분할
  const partition = (left, right) => {
    const pivot = nums[right];
    let i = left - 1;
    for (let j = left; j < right; j++) {
      if (nums[j] >= pivot) continue;
      if (nums[j] < pivot) {
        swap(++i, j);
      }
    }
    swap(++i, right); // Pivot to middle
    return i; // Pivot idx
  }
  const swap = (l, r) => {
    [nums[l], nums[r]] = [nums[r], nums[l]];
  }

  let left = 0;
  let right = nums.length - 1;
  while (true) {
    const pivotIdx = partition(left, right);
    if (nums.length - pivotIdx > k) { // 찾은 피벗이 k번째 수보다 작을 경우 피벗기준 오른쪽에서 재탐색
      left = pivotIdx + 1;
    } else if (nums.length - pivotIdx < k) { // 반대는 왼쪽에서 재탐색
      right = pivotIdx - 1;
    } else {
      return nums[pivotIdx]; // 같으면 결과 반환
    }
  }
};