Commit75ce46f

committed

add kth largest element in an array

1 parent9c2caa9 commit75ce46fCopy full SHA for 75ce46f

File tree

+33

-0

lines changed

+33

-0

lines changed

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+/**`
	`2`	`+ *@param {number[]} nums`
	`3`	`+ *@param {number} k`
	`4`	`+ *@return {number}`
	`5`	`+ */`
	`6`	`+`
	`7`	`+// use quick select`
	`8`	`+varfindKthLargest=function(nums,k){`
	`9`	`+varsmaller=[];`
	`10`	`+varlarger=[];`
	`11`	`+varpivot=nums[parseInt(nums.length/2)];`
	`12`	`+varpivotCnt=0;`
	`13`	`+`
	`14`	`+for(vari=0;i<nums.length;i++){`
	`15`	`+varnum=nums[i];`
	`16`	`+`
	`17`	`+if(num>pivot){`
	`18`	`+larger.push(num);`
	`19`	`+}elseif(num<pivot){`
	`20`	`+smaller.push(num);`
	`21`	`+}else{`
	`22`	`+pivotCnt++;`
	`23`	`+}`
	`24`	`+}`
	`25`	`+`
	`26`	`+if(k<=larger.length){// if larger includes k`
	`27`	`+returnfindKthLargest(larger,k);`
	`28`	`+}elseif(k-larger.length-pivotCnt<=0){// k is part of pivot`
	`29`	`+returnpivot;`
	`30`	`+}else{// if smaller inclues k`
	`31`	`+returnfindKthLargest(smaller,k-larger.length-pivotCnt);`
	`32`	`+}`
	`33`	`+};`

Comments

(0)