정렬 된 K 병합 연결 목록 인터뷰 관점에서 볼 때 문제는 매우 유명합니다. 이 질문은 Google, Microsoft, Amazon 등과 같은 대기업에서 여러 번 묻습니다. 이름에서 알 수 있듯이 k 개의 정렬 된 연결 목록이 제공되었습니다. 우리는 그것들을 하나로 합쳐야합니다. 단일 정렬 된 연결 목록.
더 잘 이해하기 위해 샘플 테스트 케이스를 살펴 보겠습니다.
차례
예
입력
[
1-> 2-> 3,
1-> 4-> 6,
2-> 3
]
산출
1->1->2->2->3->3->4->6
K 정렬 된 연결 목록 병합에 대한 접근 방식 -1
브 루트 포스
- 모든 연결 목록을 순회하고 모든 값을 Array / ArrayList / Vector에 넣습니다 (편리하다고 생각하는 저장소).
- 데이터 정렬
- 정렬 된 데이터에서 새 연결 목록 만들기
짜잔! 우리의 병합 및 정렬 된 연결 목록이 준비되었습니다. 코드로 더 잘 이해합시다.
자바 프로그램
class Solution
{
public ListNode mergeKLists(ListNode[] lists)
{
ListNode aux=new ListNode(0);
List<Integer>lisa=new ArrayList<Integer>();
for(int i=0;i<lists.length;i++)
{
ListNode ptr=lists[i];
while(ptr!=null)
{
lisa.add(ptr.val);
ptr=ptr.next;
}
}
Collections.sort(lisa);
ListNode ptr=aux;
for(int i=0;i<lisa.size();i++)
{
ListNode temp=new ListNode(lisa.get(i));
temp.next=null;
ptr.next=temp;
ptr=ptr.next;
}
return aux.next;
}
}
C ++ 프로그램
class Solution
{
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
vector<int>store;
for(int i=0;i<lists.size();i++)
{
ListNode *ptr=lists[i];
while(ptr!=NULL)
{
store.push_back(ptr->val);
ptr=ptr->next;
}
}
sort(store.begin(),store.end());
ListNode *ptr=new ListNode();
ListNode *aux=ptr;
for(int i=0;i<store.size();i++)
{
ListNode *temp=new ListNode(store[i]);
temp->next=NULL;
ptr->next=temp;
ptr=ptr->next;
}
return aux->next;
}
};
[ 1->2->3, 1->4->6, 2->3 ]
1->1->2->2->3->3->4->6
복잡성 분석
이제 위 솔루션의 시간 복잡성을 살펴 보겠습니다.
순회 및 생성에 걸리는 시간 : O (n)
정렬에 걸리는 시간 : O (n log n)
시간 복잡도 만들기 : O (n log n)
K 정렬 된 연결 목록 병합에 대한 접근 방식 -2
Min-Heap 사용
우선 순위 대기열을 스토리지로 사용할 수 있습니다.
장점:
- 분류 할 필요가 없습니다.
코드의 도움으로 같은 것을 살펴 보자
자바 프로그램
class Solution
{
public ListNode mergeKLists(ListNode[] lists)
{
Queue<Integer>store=new PriorityQueue();
for(int i=0;i<lists.length;i++)
{
ListNode ptr=lists[i];
while(ptr!=null)
{
store.add(ptr.val);
ptr=ptr.next;
}
}
if(store.isEmpty() )
return null;
ListNode head=new ListNode(store.poll());
ListNode cur=head;
while(!store.isEmpty())
{
ListNode temp=new ListNode(store.poll());
cur.next=temp;
cur=cur.next;
}
return head;
}
}
[ 2->5->7->9, 1->2->3->->10 ]
1->2->2->3->5->7->9->10
복잡성 분석
위의 시간 복잡도 : O (n log n)
K 정렬 된 연결 목록 병합에 대한 접근 방식 -3
분열과 정복
- 나누기 단계
목표-시간에 k / 2 함수를 병합하기 위해 k 목록을 보냅니다.
- 병합 단계
객관적인-더 작은 값을 고려하고 추가하여 새 목록을 만들려면
-
- 결합 된 목록을 반환하는 포인터 만들기
- 두 목록에서 더 작은 값을 추가하십시오.
- 값을 가져온 증가 포인터
- 두 목록에서 병합 및 정렬 된 연결 목록 반환
코드의 도움으로 더 잘 이해합시다.
자바 프로그램
class Solution
{
public static ListNode merge(ListNode l1,ListNode l2)
{
if(l1==null)
return l2;
if(l2==null)
return l1;
ListNode aux=new ListNode();
ListNode head=aux;
while(l1!=null && l2!=null)
{
if(l1.val>l2.val)
{
aux.next=l2;
l2=l2.next;
}
else
{
aux.next=l1;
l1=l1.next;
}
aux=aux.next;
}
if(l1!=null)
aux.next=l1;
else if(l2!=null)
aux.next=l2;
return head.next;
}
public static ListNode divide(ListNode[]lists,int start,int end)
{
if(end<start)
return null;
if(end==start)
return lists[start];
int mid=start+(end-start)/2;
return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
}
public ListNode mergeKLists(ListNode[] lists)
{
if(lists == null)
return null;
if(lists.length == 1)
return lists[0];
return divide(lists,0,lists.length-1);
}
}
C ++ 프로그램
class Solution
{
public:
ListNode* merge(ListNode *l1,ListNode *l2)
{
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode *aux=new ListNode();
ListNode *head=aux;
while(l1!=NULL && l2!=NULL)
{
if(l1->val>l2->val)
{
aux->next=l2;
l2=l2->next;
}
else
{
aux->next=l1;
l1=l1->next;
}
aux=aux->next;
}
if(l1!=NULL)
aux->next=l1;
else if(l2!=NULL)
aux->next=l2;
return head->next;
}
public:
ListNode* divide(vector<ListNode*>&lists,int start,int end)
{
if(end<start)
return NULL;
if(end==start)
return lists[start];
int mid=start+(end-start)/2;
return(merge(divide(lists,start,mid),divide(lists,mid+1,end)));
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
if(lists.size() == 0)
return NULL;
if(lists.size() == 1)
return lists[0];
return divide(lists,0,lists.size()-1);
}
};
[ 1->2, 3, 4->5->6->7, 8->9->10, 11 ]
1->2->3->4->5->6->7->8->9->10->11
복잡성 분석
시간 복잡도 = O (n log n)
공간 복잡도 = O (1)
