[EPI 11.8] Find the Kth largest Element

[ami-ryu]

Leetcode / p. 153

풀이 https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60306/Python-different-solutions-with-comments-(bubble-sort-selection-sort-heap-sort-and-quick-sort).

1) sorted 내장함수 : O(nlogn)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        new = sorted(nums)
        return new[-k]

2) Bubble Sort : O(nk)

• 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

  def findKthLargest2(self, nums, k):
  for i in xrange(k):
      for j in xrange(len(nums)-i-1):
          if nums[j] > nums[j+1]:
              # exchange elements, time consuming
              nums[j], nums[j+1] = nums[j+1], nums[j]
  return nums[len(nums)-k]

⭐️ 3) Quick Selection : O(n)

• O(n + n/2 + n/4 + ...) = O(n)
• 한국어 설명

  
  def findKthLargest(self, nums, k):
  # convert the kth largest to smallest
  return self.findKthSmallest(nums, len(nums)+1-k)

def findKthSmallest(self, nums, k): if nums: pos = self.partition(nums, 0, len(nums)-1) if k > pos+1: return self.findKthSmallest(nums[pos+1:], k-pos-1) elif k < pos+1: return self.findKthSmallest(nums[:pos], k) else: return nums[pos]

choose the right-most element as pivot

def partition(self, nums, l, r): low = l while l < r: if nums[l] < nums[r]: nums[l], nums[low] = nums[low], nums[l] low += 1 l += 1 nums[low], nums[r] = nums[r], nums[low] return low

- pivot 을 뽑을때 median 으로 뽑아야 worst-case인 O(n^2) 을 면하고 O(n) 으로 찾을 수 있다.

[ami-ryu]

Variant 1. 배열의 중간값 찾기

QuickSort 에서 나온 개념인 Approximate Median 찾기

• Approximate Median(A.M)을 Pivot으로 사용하면, Quick Sort 와 Quick Select에 대해서 최악의 경우를 피할 수 있다.
• 한국어 설명 : https://m.blog.naver.com/babobigi/220529081438

Approximate Median 아이디어

i) 전체배열을 작게 분할하여 분할된 배열내에서 중간값을 찾는다. ii) 각각의 분할된 배열내의 중간값들에서 중간값을 한번 더 찾는다. 그렇다면, 이는 대략적인 중간값일 것이다.

---

세 수(Triple)의 중앙값 찾기

• 한국어 풀이 : https://o-tantk.github.io/posts/finding-median/

퀵정렬을 설계할 때 Pivot을 선택하는 방법에는 여러가지가 있지만, 대표적으로는 임의의 한 원소를 선택하는 방법과 처음, 중간, 끝의 원소 중 중앙값인 원소를 선택하는 방법의 두 가지가 있다.

퀵정렬에서 써먹을 수 있도록 세 수 중에서 중앙값을 찾는 방법을 생각해보자. 기본적인 방법은, 다량의 조건문을 이용해 찾는 것이다.

int median(int a, int b, int c){
    if (a > b){
        if (b > c)          return b;
        else if (a > c)     return c;
        else                return a;
    }
    else{
        if (a > c)          return a;
        else if (b > c)     return c;
        else                return b;
    }
}

조건부 연산자(exp?exp:exp)를 이용하면 코드가 좀 더 짧아지겠지만, 해석하기 어려워 진다.

교환 법칙이 성립되는 XOR의 성질을 이용한다면, 분기 없이 중앙값을 찾을 수도 있다.

int median(int a, int b, int c){
    int maximum = max(max(a, b), c);
    int minimum = min(min(a, b), c);
    return a ^ b ^ c ^ maximium ^ minimum;
}

세 수 모두를 XOR로 결합하고, 다시 최대값 최소값을 XOR로 제외함으로써 중앙값을 구했다.

---

중요. 위에 문제와 관련해서 생각해보면, length 를 이미 알고있으므로 length/2 를 찾으면 됨.

[ami-ryu]

Variant 2. 중복값있는 배열에서 K번째 큰 요소 찾기

• k번째 큰 요소 = A{k-1] after A has been sorted in a stable manner
• 이게 같거나 큰 값은 오른쪽으로 보낸다고 하면 되는데 stable 해야하니까... 음

[1, 3, 5, 5, 7, 7, 9] k = 4

일단 퀵소트는 unstable stable 한 소팅 종류에는 Merge, Bubble, Insertion, Selection 이 있으니까.... 이런 소팅을 해서 구하면 되지 않을까?

-> http://blog.naver.com/zephyehu/150013176075

http://1ambda.github.io/algorithm/design-and-analysis-part1-2/

[ami-ryu]

Variant 3. 최소개의 메일박스 설치하기

아마도 인풋은 [10, 20, 30, 50, 100] [10, 20, 50, 100, 150]

각 거주민이 우편물까지의 거리의 전체 합이 최소가 되어야겠지.

얘네의 중간값을 찾는다고 꼭 최적인것은 아닐테고.. 음

DP 같이 풀어야하나?

---

[1명, 3명, ..] 이라면 [1, 3, 3, 3, ... ] 이런식으로 배열을 새로 만들어서 중간값을 찾는다.