23. 合并K个升序链表

题目:https://leetcode-cn.com/problems/merge-k-sorted-lists/

解法一:两两合并

  1. 我们很容易写出如何合并两个升序链表,则我们可以在合并两个升序链表的基础上改进算法合并K个升序链表
  2. 最直观的方法是:我们按照顺序,第一个链表和第二个链表合并,得到的新链表和第三个链表合并,以此类推。但这样时间复杂度较高,为$O(k^2n)$
  3. 我们可以改进我们的算法,采用类似归并排序的思想。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1==NULL){return l2;}
    if(l2==NULL){return l1;}
    struct ListNode* curr = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* dummyNode = curr;
    while(l1!=NULL && l2!=NULL){
        if(l1->val <= l2->val){
            curr->next = l1;
            curr = l1;
            l1 = l1->next;
        }else{
            curr->next = l2;
            curr = l2;
            l2 = l2->next;
        }
    }
    curr->next = (l1 == NULL ? l2 : l1);
    return dummyNode->next;
}

struct ListNode* merge(struct ListNode** lists,int left,int right){
    if(left==right) return lists[left];
    int mid = (left + right)/2;
    struct ListNode* l1 = merge(lists,left,mid);
    struct ListNode* l2 = merge(lists,mid+1,right);
    return mergeTwoLists(l1,l2);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if(listsSize==0) return NULL;
    return merge(lists,0,listsSize-1);
}

26. 删除排序数组中的重复项

题目:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

解法一:双指针 $O(n)$

  1. 维护两个指针i,j,其中一个指针指向当前元素,另一个指针指向和当前元素相同的下一个元素
  2. 那么我们基于以上假设,可以认为a[i] - a[j-1]这个区间内的所有元素都是重复的
  3. 我们用新元素直接覆盖掉前面的元素即可
class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }
        var i = 0, j = 0
        while j < nums.count {
            if nums[j] != nums[i] {
                nums[i+1] = nums[j]
                i += 1
            }         
            j += 1 
        }
        return i + 1
    }
}
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        int i = 0, j = 0;
        while(j < nums.size()){
            if(nums[j] != nums[i]){
                nums[i+1] = nums[j];
                i++;
            }
            j++;
        }
        return i + 1;
    }
};

33. 搜索旋转排序数组

题目:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

解法一:O(n)搜索旋转点,两侧各自进行二分查找。复杂度O(nlogn)

  1. 例如[4,5,6,7,0,1,2],我们找到旋转点为0,则将其分为两个数组进行二分查找[4,5,6,7][0,1,2]