Commitddefede

committed

leetcode 300LIS

1 parent9142018 commitddefedeCopy full SHA for ddefede

File tree

+104

-49

lines changed

+104

-49

lines changed

Lines changed: 51 additions & 49 deletions

Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

Lines changed: 53 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,53 @@`
	`1`	`+# -- coding:utf-8 --`
	`2`	`+'''`
	`3`	`+Given an unsorted array of integers, find the length of longest increasing subsequence.`
	`4`	`+`
	`5`	`+For example,`
	`6`	`+Given [10, 9, 2, 5, 3, 7, 101, 18],`
	`7`	`+The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.`
	`8`	`+`
	`9`	`+Your algorithm should run in O(n^2) complexity.`
	`10`	`+`
	`11`	`+Follow up: Could you improve it to O(n log n) time complexity?`
	`12`	`+'''`
	`13`	`+`
	`14`	`+`
	`15`	`+classSolution(object):`
	`16`	`+# 原始O(nlogn)方法`
	`17`	`+deflengthOfLIS(self,nums):`
	`18`	`+tails= [0]*len(nums)`
	`19`	`+size=0`
	`20`	`+forxinnums:`
	`21`	`+i,j=0,size`
	`22`	`+whilei!=j:`
	`23`	`+mid= (i+j)//2`
	`24`	`+iftails[mid]<x:`
	`25`	`+i=mid+1`
	`26`	`+else:`
	`27`	`+j=mid`
	`28`	`+tails[i]=x`
	`29`	`+size=max(i+1,size)`
	`30`	`+returnsize`
	`31`	`+# 简单优化的O(nlogn)方法, 1000000长度为8的数据平均节约0.5s`
	`32`	`+deflengthOfLIS2(self,nums):`
	`33`	`+tails= [0]*len(nums)`
	`34`	`+size=0`
	`35`	`+forxinnums:`
	`36`	`+i,j=0,size`
	`37`	`+ifj>0andtails[j-1]<x:`
	`38`	`+tails[j]=x`
	`39`	`+size+=1`
	`40`	`+continue`
	`41`	`+whilei!=j:`
	`42`	`+mid= (i+j)//2`
	`43`	`+iftails[mid]<x:`
	`44`	`+i=mid+1`
	`45`	`+else:`
	`46`	`+j=mid`
	`47`	`+tails[i]=x`
	`48`	`+size=max(i+1,size)`
	`49`	`+returnsize`
	`50`	`+`
	`51`	`+s=Solution()`
	`52`	`+aList= [3,2,4,9,10,22,15,17,23,6]`
	`53`	`+print(s.lengthOfLIS(aList),s.lengthOfLIS2(aList))`

Comments

(0)