Added

shichao-an · shichao-an · commit 3a6ffe27bfe2 · 2015-09-09T18:28:07.000-07:00
diff --git a/kth_largest_element_in_an_array/solution.py b/kth_largest_element_in_an_array/solution.py
@@ -8,6 +8,7 @@
 Note:
 You may assume k is always valid, 1 <= k <= array's length
 """
+
 import heapq
 
 class Solution(object):
@@ -25,6 +26,7 @@ def findKthLargest(self, nums, k):
             if i == k - 1:
                 return e
 
+
 a1 = [3, 2, 1, 5, 6, 4]
 s = Solution()
 res = s.findKthLargest(a1, 2)
diff --git a/kth_largest_element_in_an_array/solution2.py b/kth_largest_element_in_an_array/solution2.py
@@ -0,0 +1,50 @@
+"""
+Find the kth largest element in an unsorted array. Note that it is the kth
+largest element in the sorted order, not the kth distinct element.
+
+For example,
+Given [3,2,1,5,6,4] and k = 2, return 5.
+
+Note: You may assume k is always valid, 1 <= k <= array's length.
+"""
+
+
+class Solution(object):
+    def findKthLargest(self, nums, k):
+        """
+        :type nums: List[int]
+        :type k: int
+        :rtype: int
+
+        Quickselect: O(n)
+        """
+        left = 0
+        right = len(nums) - 1
+        while left <= right:
+            pivot = self.partition(nums, left, right)
+            # nums[pivot] is (pivot + 1)th largest, so
+            # if pivot == k - 1, it is kth largest.
+            if pivot == k - 1:
+                return nums[pivot]
+            elif pivot < k - 1:
+                left = pivot + 1
+            else:
+                right = pivot - 1
+
+    def partition(self, nums, left, right):
+        """Partition the array so that larger elements are to the left"""
+        pivot = right
+        # i is from left to right - 1
+        j = left
+        for i in range(left, right):
+            if nums[i] > nums[pivot]:
+                nums[i], nums[j] = nums[j], nums[i]
+                j += 1
+        nums[j], nums[pivot] = nums[pivot], nums[j]
+        return j
+
+
+s = Solution()
+a = [3, 2, 1, 5, 6, 4]
+
+print s.findKthLargest(a, 2)
diff --git a/search_in_rotated_sorted_array/solution2.py b/search_in_rotated_sorted_array/solution2.py
@@ -0,0 +1,41 @@
+"""
+Suppose a sorted array is rotated at some pivot unknown to you beforehand.
+
+(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
+
+You are given a target value to search. If found in the array return its
+index, otherwise return -1.
+
+You may assume no duplicate exists in the array.
+"""
+
+class Solution(object):
+    def search(self, nums, target):
+        """
+        :type nums: List[int]
+        :type target: int
+        :rtype: int
+        """
+        left = 0
+        right = len(nums) - 1
+        while left + 1 < right:
+            mid = left + (right - left) / 2
+            if target == nums[mid]:
+                return mid
+            # Right side is sorted
+            elif nums[mid] < nums[right]:
+                if nums[mid] <= target <= nums[right]:
+                    left = mid
+                else:
+                    right = mid
+            # Left side is sorted
+            else:
+                if nums[left] <= target <= nums[mid]:
+                    right = mid
+                else:
+                    left = mid
+        if nums[left] == target:
+            return left
+        elif nums[right] == target:
+            return right
+        return -1
diff --git a/search_in_rotated_sorted_array_ii/solution2.py b/search_in_rotated_sorted_array_ii/solution2.py
@@ -0,0 +1,44 @@
+"""
+Suppose a sorted array is rotated at some pivot unknown to you beforehand.
+
+(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
+
+Follow up for "Search in Rotated Sorted Array":
+
+What if duplicates are allowed?
+
+Would this affect the run-time complexity? How and why?
+
+Write a function to determine if a given target is in the array.
+"""
+
+class Solution(object):
+    def search(self, nums, target):
+        """
+        :type nums: List[int]
+        :type target: int
+        :rtype: bool
+        """
+        left = 0
+        right = len(nums) - 1
+        while left + 1 < right:
+            mid = left + (right - left) / 2
+            if target == nums[mid]:
+                return True
+            # Left part is sorted
+            elif nums[mid] > nums[right]:
+                if nums[left] <= target < nums[mid]:
+                    right = mid
+                else:
+                    left = mid
+            # Right part is sorted
+            elif nums[mid] < nums[right]:
+                if nums[mid] < target <= nums[right]:
+                    left = mid
+                else:
+                    right = mid
+            else:
+                right -= 1
+        if nums[left] == target or nums[right] == target:
+            return True
+        return False
