过是过了。。感觉时间复杂度上还是不太对= =。。
因为排序已经用了o(n)级别的复杂度。再次遍历一遍 又是o(n)复杂度。所以2n。还是o(n)级别?
func longestConsecutive(_ nums: [Int]) -> Int {
let len = nums.count
if len == 0 {
return 0
}
let sortNums = nums.sorted()
var ans = 1
var temp = 1
for i in 1..<len {
let v1 = sortNums[i]
let v2 = sortNums[i - 1]
if v1 == v2 {
continue
}
if v1 - v2 == 1 {
temp += 1
ans = max(ans,temp)
}else{
temp = 1
}
}
return ans
}
}
并查集。。 感觉有点牵强。。要用字典去重。。
但是这个只是用字典就能解决的= =。
class Solution {
class MyUnionFindSize {
var parents = [Int]()
var sizes = [Int]()
init(_ capacity:Int){
sizes = Array.init(repeating: 1, count: capacity)
for i in 0..<capacity{
parents.append(i)
}
}
func find(_ v:Int)-> Int {
//路径减半
var temp = v
while temp != parents[temp] {
parents[temp] = parents[parents[temp]]
temp = parents[temp]
}
return temp
}
func union(_ v1:Int,_ v2:Int) {
let p1 = find(v1)
let p2 = find(v2)
if p1 == p2 {
return
}
let s1 = sizes[p1]
let s2 = sizes[p2]
if s1 < s2 {
parents[p1] = p2
sizes[p2] += sizes[p1]
}else {
parents[p2] = p1
sizes[p1] += sizes[p2]
}
}
}
func longestConsecutive(_ nums: [Int]) -> Int {
let len = nums.count
if len == 0 {
return 0
}
var map = [Int:Int]()
//初始化并查集
let uf = MyUnionFindSize(len)
for i in 0..<len {
let num = nums[i]
if let _ = map[num] {
continue
}
if let temp = map[num + 1] {
uf.union(i, temp);
}
if let temp = map[num - 1] {
uf.union(i, temp);
}
map[num] = i
}
return uf.sizes.max()!
}
}
字典的方法
func longestConsecutive(_ nums: [Int]) -> Int {
let len = nums.count
if len == 0 {
return 0
}
var map = [Int:Int]()
var ans = 1
for num in nums {
map[num] = 1
}
for num in nums {
if let _ = map[num - 1] {
continue
}
var tempNum = num
var tempLen = 1
while map[tempNum + 1] == 1 {
tempNum += 1
tempLen += 1
}
ans = max(ans, tempLen)
}
return ans
}
网友评论