kth_largest_element_in_an_array

hitzzc · hitzzc · commit 9fab52c88c18 · 2016-10-16T23:52:40.000+08:00
diff --git a/README.md b/README.md
@@ -172,6 +172,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [211. Add and Search Word - Data structure design](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
 #### [213. House Robber II](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
 #### [214. Shortest Palindrome (unsolved)](https://github.com/hitzzc/go-leetcode/tree/master/shortest_palindrome)
+#### [215. Kth Largest Element in an Array](https://github.com/hitzzc/go-leetcode/tree/master/kth_largest_element_in_an_array)
 
 
 
diff --git a/kth_largest_element_in_an_array/kth_largest_element_in_an_array.go b/kth_largest_element_in_an_array/kth_largest_element_in_an_array.go
@@ -0,0 +1,23 @@
+package kth_largest_element_in_an_array
+
+func findKthLargest(nums []int, k int) int {
+	return partition(nums, 0, len(nums)-1, k)
+}
+
+func partition(nums []int, i, j, k int) (ret int) {
+	p := i
+	for m := i; m < j; m++ {
+		if nums[m] > nums[j] {
+			nums[p], nums[m] = nums[m], nums[p]
+			p++
+		}
+	}
+	nums[p], nums[j] = nums[j], nums[p]
+	if p+1 == k {
+		return nums[p]
+	}
+	if k < p+1 {
+		return partition(nums, i, p-1, k)
+	}
+	return partition(nums, p+1, j, k)
+}
