問題描述
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,Given [10, 9, 2, 5, 3, 7, 101, 18],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.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
問題分析
- 動規(guī)办陷，復(fù)雜度O(n2)**
-
覆蓋方法抓半，復(fù)雜度O(n log n)**
參考了這篇文章福扬。
這種方法的解題步驟是：
-將第1個數(shù)字加入解集一罩；
-依次讀取后面的數(shù)字腺占，如果此數(shù)字比解集中最后一個數(shù)字大，則將此數(shù)字追加到解集后沪猴，否則麸俘，用這個數(shù)字替換解集中第一個比此數(shù)字大的數(shù)，解集是有序的吵瞻，因此查找可以用二分法葛菇，復(fù)雜度O(log n)；
-最后的答案是解集的長度（而解集中保存的并不一定是合法解）橡羞。
舉個栗子眯停，輸入為[1,4,6,2,3,5]：
-解集初始化為[1]；
-讀到4卿泽，將其追加到解集中莺债，解集變?yōu)閇1,4]；
-讀到6签夭，將其追加到解集中齐邦，解集變?yōu)閇1,4,6]；
-讀到2第租，用其替換解集中的4措拇，解集變?yōu)閇1,2,6]，注意此時解集不是一個合法解慎宾，因為2是在6后出現(xiàn)的丐吓，但是解集的長度始終標識著當前最長序列的長度；
-讀到3趟据，用其替換解集中的6券犁，解集變?yōu)閇1,2,3]；
-讀到5汹碱，將其追加到解集中粘衬，解集變?yōu)閇1,2,3,5]，得到答案為解集長度4咳促。
【兩種方法效率差異很大色难！】
AC代碼
動規(guī)
Runtime: 1068 ms, which beats 47.56% of Python submissions.
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
rst = [-1 for i in range(n)]
rst[-1] = 1
opt = 1
for i in range(n-2, -1, -1):
m = 1
for j in range(i+1, n):
if nums[j] > nums[i] and rst[j] + 1 > m:
m = rst[j] + 1
rst[i] = m
if m > opt:
opt = m
return opt
覆蓋
Runtime: 44 ms, which beats 94.09% of Python submissions.
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
rst = [nums[0]]
for i in range(1, n):
if nums[i] > rst[-1]:
rst.append(nums[i])
else:
index = self.midSearch(rst, nums[i])
rst[index] = nums[i]
return len(rst)
def midSearch(self, s, k):
p = 0
q = len(s) - 1
while(p <= q):
m = (p + q)/2
if s[m] == k:
return m
if s[m] > k:
q = m - 1
else:
p = m + 1
return p
