Commitbce14ac

committed

resume cracking starts from 215

1 parent8a7e3a3 commitbce14acCopy full SHA for bce14ac

File tree

+53

-0

lines changed

+53

-0

lines changed

Lines changed: 52 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,52 @@`
	`1`	`+/**`
	`2`	`+ * Key:`
	`3`	`+ * Quick select algorithm, choose last element of the array as the pivot.`
	`4`	`+ * Move all smaller elements than the pivot to the left of the pivot,`
	`5`	`+ * move all bigger elements than the pivot to the right of the pivot,`
	`6`	`+ * repeat this process until the pivot is K`
	`7`	`+ * O(N)? worst O(N^2)`
	`8`	`+ *`
	`9`	`+ *@param {number[]} nums`
	`10`	`+ *@param {number} k`
	`11`	`+ *@return {number}`
	`12`	`+ */`
	`13`	`+varfindKthLargest=function(nums,k){`
	`14`	`+k=nums.length-k;`
	`15`	`+varstart=0;`
	`16`	`+varend=nums.length-1;`
	`17`	`+while(start<=end){`
	`18`	`+varpivot=partition(nums,start,end);`
	`19`	`+if(k===pivot){`
	`20`	`+returnnums[pivot];`
	`21`	`+}`
	`22`	`+elseif(k<pivot){`
	`23`	`+end=pivot-1;`
	`24`	`+}else{`
	`25`	`+start=pivot+1;`
	`26`	`+}`
	`27`	`+}`
	`28`	`+};`
	`29`	`+`
	`30`	`+varpartition=function(nums,start,end){`
	`31`	`+varleft=start;`
	`32`	`+varright=end;`
	`33`	`+varpivot=end;`
	`34`	`+while(true){`
	`35`	`+while(left<right&&nums[left]<nums[pivot]){`
	`36`	`+left++;`
	`37`	`+}`
	`38`	`+while(left<right&&nums[right]>=nums[pivot]){`
	`39`	`+right--;`
	`40`	`+}`
	`41`	`+if(left===right)break;`
	`42`	`+swap(nums,left,right);`
	`43`	`+}`
	`44`	`+swap(nums,right,end);`
	`45`	`+returnright;`
	`46`	`+};`
	`47`	`+`
	`48`	`+varswap=function(nums,i,j){`
	`49`	`+vartmp=nums[i];`
	`50`	`+nums[i]=nums[j];`
	`51`	`+nums[j]=tmp;`
	`52`	`+};`

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -95,6 +95,7 @@`
`95`	`95`	`*[162. Find Peak Element](https://leetcode.com/problems/find-peak-element/) -[Solution](./Medium/162-findPeakElement.js)`
`96`	`96`	`*[199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/) -[Solution](./Medium/199-binaryTreeRightSideView.js)`
`97`	`97`	`*[213. House Robber II](https://leetcode.com/problems/house-robber-ii/) -[Solution](./Medium/213-houseRobberII.js)`
	`98`	`+*[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) -[Solution](./Medium/215-KthLargestElementInArray.js)`
`98`	`99`	`*[230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) -[Solution](./Medium/230-kthSmallestElementinBST.js)`
`99`	`100`	`*[238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) -[Solution](./Medium/238-productExceptSelf.js)`
`100`	`101`	`*[240. Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/) -[Solution](./Medium/240-Search2DMatrixII.js)`

Comments

(0)