update

andyheko · andyheko · commit 375a5042bf98 · 2020-06-24T15:04:43.000-07:00
diff --git a/215_Kth Largest Element in an Array.py b/215_Kth Largest Element in an Array.py
@@ -0,0 +1,29 @@
+class Solution:
+    def findKthLargest(self, nums: List[int], k: int) -> int:
+        nums.sort()
+        return nums[-k]
+class Solution:
+    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
diff --git a/Array/031_Next Permutation.py b/Array/031_Next Permutation.py
@@ -0,0 +1,28 @@
+class Solution:
+    def nextPermutation(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        right = len(nums) - 1
+
+        # find longest non-increasing suffix from rightmost
+        while right >= 1 and nums[right-1] >= nums[right]:
+            right -= 1
+        if right == 0: # while nums is descending
+            return nums.reverse()
+
+        # find pivot
+        pivot = right - 1
+        # find rightmost succesor which > pivot
+        for i in range(len(nums)-1, pivot, -1):
+            if nums[i] > nums[pivot]:
+                successor = i
+                break
+        # swap pivot and successor
+        nums[pivot], nums[successor] = nums[successor], nums[pivot]
+        # reverse suffix
+        l, r = pivot+1, len(nums)-1
+        while l < r:
+            nums[l], nums[r] = nums[r], nums[l]
+            l += 1
+            r -= 1
