8.排序数组常见算法

---

前几个题比较简单，最后一个合并K个有序数组，不熟悉STL模板的童鞋可能会抓狂，不要紧，我已经添加了详细的注释，只要认真看下去认真思考，相信你可以的！

Remove Duplicates from Sorted Array I,II

对有序数组去重

每个元素只能出现一次

Remove Duplicates from Sorted Array I

问题描述：给你一个排好序的数组，去掉重复的元素保证每个元素只出现一次。不允许使用另外一个数组来提供额外的空间，你必须在原数组中进行这个工作。

解题思路：董老师这里运用了fast,low两个值，只有当下一个元素与上一个唯一元素不重复时slow才加1，slow实际存储的去重后新数组的长度，而fast是用来遍历数组的，当fast超过数组的size时，即意味着遍历结束，我们的去重工作完成。由于原题要求不允许使用额外的空间，所以下面的解法是直接对已重复的元素所在地址进行覆盖，后面的会被直接移到前面。

示例代码

/*
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;
    }
}

如果我们允许每个元素可以出现至少两次呢？

Remove Duplicates from Sorted Array II

很简单，我们加个标志位来记录元素的重复次数就好了，当重复次数超过两次时我们再进行去重处理。

示例代码：

/*
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

在有序数组中找交集：

array1:[2 3 4 6]  
array2:[3 6 9 10]  

return [3,6]

解题思路：遍历比较A、B两数组中的元素，如果出现相等的元素便将该值加入到新的数组中。无疑，用vector这种动态容器来充当新数组是最好的。

示例代码：

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

合并有序数组

1.Merge Two Sorted Array into a new Array
2.Merge Two Sorted Array A and B into A, assume A has enough space.

解题思路：董老师的程序是将组合后的新元素塞到了数组B里面。大致思路就是我们要想让B成为合并后的新数组，就必须确保B多余的空间大于等于A数组的长度，所以下面代码给A定了n的长度，而B为2*n。B从第n位开始都初始化为0，意味着后面是可以用来被重新赋值覆盖的。在填充新的数组B的时候，为了不将前面的元素覆盖，我们从后往前填充数组。

示例代码：

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.

在该题中，董老师用到了优先队列，这里我简单介绍下它的概念。

priority_queue的模板声明带有三个参数:
priority_queue<Type, Container, Functional>
其中Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container必须是用数组实现的容器，比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

优先队列中元素出队列的顺序由元素的优先级决定，而不是元素进入队列的次序 ，

例如：我们常用的操作就是对数据排序，优先队列默认的是数据大的优先级高，所以我们无论按照什么顺序push一堆数，最终在队列里总是top出最大的元素。

这里需要重点说明的是当你使用priority_queue来push数据的时候，你录入的数据并不会进行排序，只有当你pop数据的时候，priority_queue才会根据Functional规定的数据优先级来弹出优先级最高的那个数据。

解题思路：利用最小堆这种数据结构，我们首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把刚刚被取出元素的那个链表的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时k个链表也合并为了一个链表，返回首节点即可，注意head(存储最终结果的链表头)跟heap(最小堆)不要混淆。

示例代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


//重载操作符，定义优先级为数据越小优先级越大
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;

    //将每个链表中的头结点（即每个数组开头最小的值）压入堆中
    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最小堆中的数据，并将那个数据填入到新链表中
    //直到堆中数据为空，停止循环
    while (!heap.empty()) {
        //curNode始终代表了堆中最小的那个数据节点
        curNode = heap.top();
        heap.pop();

        //第一次循环，head指向了堆中最小的数据
        if (head == NULL) {
            head = curNode;
        }

        //如果那个最小的数据所在的链表后面还有数据，那就将他后面的数据压入堆中
        if (curNode->next) {
            heap.push(curNode->next);
        }

        //定义前一个节点用于新链表的迭代更新，
        //第二次prevNode已存在，curNode（新的最小数据）会被接入到prevNode的后面，链表在不断地被填入新的数据
        if (prevNode) {
            prevNode->next = curNode;
        }
        prevNode = curNode;
    }

    //返回我们新链表的头结点，合并K个数组工作完成
    return head;
}

---