Commitea4643a

committed

solves kth largest element in array in java

1 parent3982b6d commitea4643aCopy full SHA for ea4643a

File tree

+35

-1

lines changed

+35

-1

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -172,7 +172,7 @@`
`172`	`172`	`\| 210\|[Course Schedule II](https://leetcode.com/problems/course-schedule-ii)\|\|\|`
`173`	`173`	`\| 211\|[Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure)\|\|\|`
`174`	`174`	`\| 213\|[House Robber II](https://leetcode.com/problems/house-robber-ii)\|\|\|`
`175`		`-\| 215\|[Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array)\|\|\|`
	`175`	`+\| 215\|[Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array)\|[![Java](assets/java.png)](src/KthLargestElementInAnArray.java)\|\|`
`176`	`176`	`\| 216\|[Combination Sum III](https://leetcode.com/problems/combination-sum-iii)\|\|\|`
`177`	`177`	`\| 217\|[Contains Duplicate](https://leetcode.com/problems/contains-duplicate)\|[![Java](assets/java.png)](src/ContainsDuplicate.java)[![Python](assets/python.png)](python/contains_duplicate.py)\|\|`
`178`	`178`	`\| 219\|[Contains Duplicate II](https://leetcode.com/problems/contains-duplicate-ii)\|[![Java](assets/java.png)](src/ContainsDuplicateII.java)[![Python](assets/python.png)](python/contains_duplicate_ii.py)\|\|`

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,34 @@`
	`1`	`+// https://leetcode.com/problems/kth-largest-element-in-an-array`
	`2`	`+// T: O(n)`
	`3`	`+// S: O(1)`
	`4`	`+`
	`5`	`+publicclassKthLargestElementInAnArray {`
	`6`	`+publicintfindKthLargest(int[]nums,intk) {`
	`7`	`+intpartitionIndex =nums.length -k;`
	`8`	`+for (intleft =0,right =nums.length -1,j ;left <right ; ) {`
	`9`	`+j =partition(nums,left,right);`
	`10`	`+if (j ==partitionIndex)returnnums[partitionIndex];`
	`11`	`+elseif (j <partitionIndex)left =j +1;`
	`12`	`+elseright =j -1;`
	`13`	`+ }`
	`14`	`+returnnums[partitionIndex];`
	`15`	`+ }`
	`16`	`+`
	`17`	`+privateintpartition(int[]array,intleft,intright) {`
	`18`	`+intpivot =array[right],i =left -1;`
	`19`	`+for (intj =left ;j <right ;j++) {`
	`20`	`+if (array[j] <pivot) {`
	`21`	`+i++;`
	`22`	`+swap(array,i,j);`
	`23`	`+ }`
	`24`	`+ }`
	`25`	`+swap(array,i +1,right);`
	`26`	`+returni +1;`
	`27`	`+ }`
	`28`	`+`
	`29`	`+privatevoidswap(int[]array,inti,intj) {`
	`30`	`+inttemp =array[i];`
	`31`	`+array[i] =array[j];`
	`32`	`+array[j] =temp;`
	`33`	`+ }`
	`34`	`+}`

Comments

(0)