Swift - LeetCode - K 개의 정렬 링크 통합
K 개 정렬 링크 병합
질문:
k 개의 정렬 링크 를 합 쳐 합 친 정렬 링크 를 되 돌려 줍 니 다.알고리즘 의 복잡 도 를 분석 하고 설명 하 십시오.
문제 풀이 방향:
여 긴 분 치 법 이 필요 해.쉽게 말 하면 쉬 지 않 고 반 으로 나 누 는 것 이다. 예 를 들 어 k 개의 링크 는 먼저 두 개의 k / 2 개의 링크 를 합병 하 는 임무 로 나 누고 한 개 또는 두 개의 링크 만 있 는 임무 로 나 눌 때 까지 계속 아래로 나 누 어 합병 하기 시작한다.예 를 들 어 6 개의 링크 를 합병 하면 분 치 법 에 따라 우 리 는 먼저 1 과 4, 2 와 5, 3 과 6 을 합병 한다.이렇게 하면 다음 에는 3 개의 링크 만 합병 하면 우 리 는 1 과 3 을 합병 하고 마지막 에 2 와 합병 하면 된다.
예시:
:
[
1->4->5,
1->3->4,
2->6
]
: 1->1->2->3->4->4->5->6
코드:
/**
public class SingNode {
public var value : Int
public var nextNode: SingNode?
public init(value:Int) {
self.value = value
}
}
**/
func merchageTotalList(_ list : [SingNode?]) -> SingNode? {
guard list.count > 0 else {
return nil
}
var left = 0
var right = list.count - 1
var lists = list
while right > 0 {
left = 0
while left < right {
lists[left] = merchgeTwoList(lists[left], lists[right])
left = left + 1
right = right - 1
}
}
return lists[0]
}
func merchgeTwoList(_ l1:SingNode?, _ l2:SingNode?) -> SingNode? {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
let dummy = SingNode.init(value: 0)
var tempNode = dummy
var L1 = l1
var L2 = l2
while L1 != nil && L2 != nil {
if L1!.value < L2!.value {
tempNode.nextNode = L1
L1 = L1?.nextNode
} else {
tempNode.nextNode = L2
L2 = L2?.nextNode
}
tempNode = tempNode.nextNode!
}
tempNode.nextNode = L1 ?? L2
return dummy.nextNode
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.