• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode300.最长上升子序列|LongestIncreasingSubsequence

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10241381.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

  • 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?


给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?


16ms

 1 class Solution {
 2     func lengthOfLIS(_ nums: [Int]) -> Int {
 3         if nums.count < 2 {
 4             return nums.count
 5         }
 6         var res = Array(repeating: 0, count: nums.count)
 7         res[0] = nums[0]
 8         var count = 1
 9         var j = 0
10         for i in 0..<nums.count {
11             let tmp = nums[i]
12             if tmp > res[count - 1] {
13                 j = count
14                 count += 1
15             }else {
16                 var left = 0
17                 var right = count - 1
18                 while left < right {
19                     let mid = (left + right) / 2
20                     if res[mid] >= nums[i] {
21                         right = mid
22                     }else {
23                         left = mid + 1
24                     }
25                 }
26                 j = left
27             }
28             res[j] = nums[i]
29         }
30         return count
31     }
32 }

56ms

 1 class Solution {
 2     func lengthOfLIS(_ nums: [Int]) -> Int {
 3         var results = [Int]()
 4         for num in nums {
 5             var needAdd = true
 6             if results.count > 0 {
 7                 for index in 0..<results.count {
 8                     if num <= results[index] {
 9                         results[index] = num
10                         needAdd = false
11                         break
12                     }
13                 }
14             }
15             if needAdd {
16                 results.append(num)
17             }
18         }
19         return results.count
20     }
21 }

300ms

 1 class Solution {
 2     func lengthOfLIS(_ nums: [Int]) -> Int {
 3         guard !nums.isEmpty else {
 4             return 0
 5         }
 6         
 7         var dps = Array(repeating: 1, count: nums.count)
 8         var result = 1
 9         for index in 1..<nums.count {
10             let num = nums[index]
11             for j in 0..<index {
12                 if num > nums[j] {
13                     let length = dps[j] + 1
14                     if length > dps[index] {
15                         dps[index] = length
16                         result = max(result, dps[index])
17                     }
18                 }
19             }
20         }
21 
22         return result
23     }
24 }

312ms

 1 class Solution {
 2     func lengthOfLIS(_ nums: [Int]) -> Int {
 3          var length_global = 0
 4     var length_current = [Int].init(repeating:1 , count: nums.count)
 5     
 6     for i in 0..<nums.count {
 7         for j in 0..<i {
 8             if nums[i] > nums[j] {
 9                 length_current[i] = max(length_current[i], length_current[j] + 1)
10             }
11         }
12         length_global = max(length_global, length_current[i])
13     }
14     
15     return length_global
16     }
17 }

376ms

 1 class Solution {
 2     func lengthOfLIS(_ nums: [Int]) -> Int {
 3         guard !nums.isEmpty else {
 4             return 0
 5         }
 6         
 7         var dps = Array(repeating: 1, count: nums.count)
 8         var result = 1
 9         for index in 1..<nums.count {
10             let num = nums[index]
11             for j in 0..<index where num > nums[j] {
12                 let length = dps[j] + 1
13                 dps[index] = max(length, dps[index])
14                 result = max(result, dps[index])
15             }
16         }
17 
18         return result
19     }
20 }

388ms

 1 class Solution {
 2     func lengthOfLIS(_ nums: [Int]) -> Int {
 3         
 4         if nums.count == 0 {
 5             return 0
 6         }
 7         
 8         var result = 1
 9         var dArr = [Int](repeating: 1, count: nums.count)
10         
11         for i in 0..<nums.count {
12 
13             for j in 0..<i {
14                 
15                 if(nums[j] < nums[i] && (dArr[j] + 1 >= dArr[i])) {
16                     dArr[i] = dArr[j] + 1
17                 }
18             }
19             result = dArr[i] > result ? dArr[i] : result
20         }
21         return result
22     }
23 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift设置只读(readOnly)属性发布时间:2022-07-13
下一篇:
[Swift]理解并获取mimeType类型发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap