我正在解决这个leetcode问题链接,我们需要在列表或数组中找到最长的递增子序列。我使用了两种方法来解决这个问题。
- 首先使用
while
循环 - 使用嵌套的
for
循环
尽管(i, j)或循环的值完全相同,但对于更高长度的输入,
while循环
程序比for循环
程序花费更多时间。 我不确定为什么?
FOR循环
import time
start_time = time.time()
class Solution(object):
# using dP
def lengthOfLIS1(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print Solution().lengthOfLIS1([1] * 1249 + [101] + [1] * 1250)
print("--- %s seconds ---" % (time.time() - start_time))
输出:
2
--- 0.240112066269 seconds ---
WHILE LOOP
# This problem an be done in O(n*n)
import time
start_time = time.time()
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return []
elif len(nums) == 1:
return nums
size = len(nums)
subsequence_array = [1] * size
i, j, max_value = 0, 1, 1
while j < size:
if nums[j] > nums[i]:
subsequence_array[j] = max(subsequence_array[j], subsequence_array[i] + 1)
if max_value < subsequence_array[j]:
max_value = subsequence_array[j]
i += 1
if j == i:
i = 0
j += 1
else:
i += 1
if i == j:
j += 1
i = 0
return max_value
print Solution().lengthOfLIS([1] * 1249 + [101] + [1] * 1250)
print("--- %s seconds ---" % (time.time() - start_time))
输出
2
--- 0.331799030304 seconds ---
有人能解释一下为什么while循环
花费的时间比for循环
还要长,尽管对i和j
的循环几乎是相同的吗?期待您的回答。
while
循环时间更长的解释。 - python