Commit6be9c09

committed

Several possible approaches

1 parent29df8e9 commit6be9c09Copy full SHA for 6be9c09

File tree

+44

-0

lines changed

+44

-0

lines changed

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+# @param {Integer[]} nums`
	`2`	`+# @return {Integer}a`
	`3`	`+`
	`4`	`+#shortest solution O(n)?`
	`5`	`+deffind_min(nums)`
	`6`	`+nums.min`
	`7`	`+end`
	`8`	`+`
	`9`	`+#non binary-search iterative approach O(n)`
	`10`	`+deffind_min(nums)`
	`11`	`+last_num=nums.last`
	`12`	`+nums.each.with_indexdo \|num,i\|`
	`13`	`+returnnumifnum <=last_num`
	`14`	`+end`
	`15`	`+end`
	`16`	`+`
	`17`	`+#using ruby's built-in binary search O(log n)`
	`18`	`+deffind_min(nums)`
	`19`	`+nums.bsearch{\|num\|num <=nums.last}`
	`20`	`+end`
	`21`	`+`
	`22`	`+#custom binary-search O(log n)`
	`23`	`+deffind_min(nums)`
	`24`	`+result=nums[0]`
	`25`	`+left=0`
	`26`	`+right=nums.length -1`
	`27`	`+`
	`28`	`+whileleft <=rightdo`
	`29`	`+ifnums[left] <nums[right]`
	`30`	`+return[result,nums[left]].min`
	`31`	`+end`
	`32`	`+`
	`33`	`+mid=(left +right) /2`
	`34`	`+result=[result,nums[mid]].min`
	`35`	`+`
	`36`	`+ifnums[mid] >=nums[left]`
	`37`	`+left=mid +1`
	`38`	`+else`
	`39`	`+right=mid -1`
	`40`	`+end`
	`41`	`+end`
	`42`	`+`
	`43`	`+returnresult`
	`44`	`+end`

Comments

(0)