前幾個題比較簡單，最后一個合并K個有序數(shù)組陶贼，不熟悉STL模板的童鞋可能會抓狂，不要緊扣溺，我已經(jīng)添加了詳細(xì)的注釋骇窍，只要認(rèn)真看下去認(rèn)真思考，相信你可以的锥余！
Remove Duplicates from Sorted Array I,II
對有序數(shù)組去重
每個元素只能出現(xiàn)一次
Remove Duplicates from Sorted Array I
問題描述：給你一個排好序的數(shù)組腹纳，去掉重復(fù)的元素保證每個元素只出現(xiàn)一次。不允許使用另外一個數(shù)組來提供額外的空間驱犹，你必須在原數(shù)組中進(jìn)行這個工作嘲恍。
解題思路：董老師這里運(yùn)用了fast,low兩個值，只有當(dāng)下一個元素與上一個唯一元素不重復(fù)時slow才加1雄驹，slow實(shí)際存儲的去重后新數(shù)組的長度佃牛，而fast是用來遍歷數(shù)組的，當(dāng)fast超過數(shù)組的size時医舆，即意味著遍歷結(jié)束俘侠，我們的去重工作完成象缀。由于原題要求不允許使用額外的空間，所以下面的解法是直接對已重復(fù)的元素所在地址進(jìn)行覆蓋爷速，后面的會被直接移到前面央星。
示例代碼
/*
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
*/
public class Solution {
public int removeDuplicates(int[] A) {
int size = A.length;
if (size <= 1)
return size;
int fast = 1;
int slow = 0;
while ( fast < size) {
if (A[slow] != A[fast]) {
A[slow+1] = A[fast];
slow++;
}
fast++;
}
return slow+1;
}
}
如果我們允許每個元素可以出現(xiàn)至少兩次呢？
Remove Duplicates from Sorted Array II
很簡單惫东，我們加個標(biāo)志位來記錄元素的重復(fù)次數(shù)就好了莉给，當(dāng)重復(fù)次數(shù)超過兩次時我們再進(jìn)行去重處理。
示例代碼：
/*
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
*/
public class Solution {
public int removeDuplicates(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int size = A.length;
if (size <= 1)
return size;
int fast = 1;
int slow = 0;
int dup = 0;
while ( fast < size) {
if (A[slow] != A[fast]) {
A[slow+1] = A[fast];
slow++;
dup = 0;
} else{
dup++;
if (dup < 2) {
A[slow+1] = A[fast];
slow++;
}
}
fast++;
}
return slow+1;
}
}
Intersection of 2 sorted array
在有序數(shù)組中找交集：
array1:[2 3 4 6]
array2:[3 6 9 10]
return [3,6]
解題思路：遍歷比較A廉沮、B兩數(shù)組中的元素颓遏，如果出現(xiàn)相等的元素便將該值加入到新的數(shù)組中。無疑滞时，用vector這種動態(tài)容器來充當(dāng)新數(shù)組是最好的叁幢。
示例代碼：
vector<int> findIntersection(vector<int> A, vector<int> B) {
vector<int> intersection;
int n1 = A.size();
int n2 = B.size();
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (A[i] > B[j]) {
j++;
} else if (B[j] > A[i]) {
i++;
} else {
intersection.push_back(A[i]);
i++;
j++;
}
}
return intersection;
}
Merge Sorted Array
合并有序數(shù)組
1.Merge Two Sorted Array into a new Array
2.Merge Two Sorted Array A and B into A, assume A has enough space.
解題思路：董老師的程序是將組合后的新元素塞到了數(shù)組B里面。大致思路就是我們要想讓B成為合并后的新數(shù)組漂洋，就必須確保B多余的空間大于等于A數(shù)組的長度遥皂，所以下面代碼給A定了n的長度，而B為2*n刽漂。B從第n位開始都初始化為0，意味著后面是可以用來被重新賦值覆蓋的弟孟。在填充新的數(shù)組B的時候贝咙，為了不將前面的元素覆蓋，我們從后往前填充數(shù)組拂募。
示例代碼：
Set A[n] = {2, 11, 54, 87, 99}
Set B[2*n] = = {4, 9, 34, 67, 98, 0, 0, 0, 0, 0}
void Merge(int A[], int B[], int size_b, int n) {
indexA=n -1;
indexB=n -1;
index_new=2n -1;
while (index_new >= 0) {
if (A[indexA] < B[indexB]) {
B[index_new] = B[indexB];
indexB--;
index_new--;
}
else {
B[index_new] = A[indexA];
indexA--;
index_new--;
}
// Optimization if A or B can be directly copied
//如果B原有的元素為空庭猩，那么直接像B中填充即可
if (indexB == -1) {
while(index_new >= 0)
B[index_new--] = A[indexA--];
break;
}
//如果A為空，那沒必要合并了
else if (indexA == -1)
break;
}
}
Merge K Sorted List
Merge k sorted linked lists to be one sorted list.
在該題中陈症，董老師用到了優(yōu)先隊(duì)列蔼水，這里我簡單介紹下它的概念。
priority_queue的模板聲明帶有三個參數(shù):
priority_queue<Type, Container, Functional>
其中Type 為數(shù)據(jù)類型录肯， Container 為保存數(shù)據(jù)的容器趴腋，F(xiàn)unctional 為元素比較方式。
Container必須是用數(shù)組實(shí)現(xiàn)的容器论咏，比如 vector, deque 但不能用 list.
STL里面默認(rèn)用的是 vector. 比較方式默認(rèn)用 operator< , 所以如果你把后面?zhèn)z個參數(shù)缺省的話优炬，優(yōu)先隊(duì)列就是大頂堆，隊(duì)頭元素最大谢揪。
優(yōu)先隊(duì)列中元素出隊(duì)列的順序由元素的優(yōu)先級決定绣张，而不是元素進(jìn)入隊(duì)列的次序 必怜，
例如：我們常用的操作就是對數(shù)據(jù)排序，優(yōu)先隊(duì)列默認(rèn)的是數(shù)據(jù)大的優(yōu)先級高葵硕，所以我們無論按照什么順序push一堆數(shù)眉抬，最終在隊(duì)列里總是top出最大的元素。
這里需要重點(diǎn)說明的是當(dāng)你使用priority_queue來push數(shù)據(jù)的時候懈凹，你錄入的數(shù)據(jù)并不會進(jìn)行排序吐辙，只有當(dāng)你pop數(shù)據(jù)的時候，priority_queue才會根據(jù)Functional規(guī)定的數(shù)據(jù)優(yōu)先級來彈出優(yōu)先級最高的那個數(shù)據(jù)蘸劈。
解題思路：利用最小堆這種數(shù)據(jù)結(jié)構(gòu)昏苏，我們首先把k個鏈表的首元素都加入最小堆中，它們會自動排好序威沫。然后我們每次取出最小的那個元素加入我們最終結(jié)果的鏈表中贤惯，然后把剛剛被取出元素的那個鏈表的下一個元素再加入堆中，下次仍從堆中取出最小的元素做相同的操作棒掠，以此類推孵构，直到堆中沒有元素了，此時k個鏈表也合并為了一個鏈表烟很，返回首節(jié)點(diǎn)即可颈墅，注意head(存儲最終結(jié)果的鏈表頭)跟heap(最小堆)不要混淆。
示例代碼如下：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
//重載操作符雾袱，定義優(yōu)先級為數(shù)據(jù)越小優(yōu)先級越大
struct cmp {
bool operator() (const ListNode *a, const ListNode *b)
{
if (a->val < b->val)
return false;
else
return true;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode *, vector<ListNode *>, cmp> heap;
//將每個鏈表中的頭結(jié)點(diǎn)（即每個數(shù)組開頭最小的值）壓入堆中
for (int i = 0; i < lists.size(); i++) {
if (lists[i]) {
// for the corner case: [{}]
heap.push(lists[i]);
}
}
ListNode *prevNode = NULL;
ListNode *head = NULL;
ListNode *curNode = NULL;
//不但pop最小堆中的數(shù)據(jù)恤筛，并將那個數(shù)據(jù)填入到新鏈表中
//直到堆中數(shù)據(jù)為空，停止循環(huán)
while (!heap.empty()) {
//curNode始終代表了堆中最小的那個數(shù)據(jù)節(jié)點(diǎn)
curNode = heap.top();
heap.pop();
//第一次循環(huán)芹橡，head指向了堆中最小的數(shù)據(jù)
if (head == NULL) {
head = curNode;
}
//如果那個最小的數(shù)據(jù)所在的鏈表后面還有數(shù)據(jù)毒坛，那就將他后面的數(shù)據(jù)壓入堆中
if (curNode->next) {
heap.push(curNode->next);
}
//定義前一個節(jié)點(diǎn)用于新鏈表的迭代更新，
//第二次prevNode已存在林说，curNode（新的最小數(shù)據(jù)）會被接入到prevNode的后面煎殷，鏈表在不斷地被填入新的數(shù)據(jù)
if (prevNode) {
prevNode->next = curNode;
}
prevNode = curNode;
}
//返回我們新鏈表的頭結(jié)點(diǎn)，合并K個數(shù)組工作完成
return head;
}
