力扣初級(jí)算法（五）【排序和搜索】

本文中的題目均來自力扣，代碼默認(rèn)以C#實(shí)現(xiàn)，偽代碼僅用來幫助描述，不嚴(yán)格遵循某種語言的語法。

本章涵蓋了在有序結(jié)構(gòu)中的排序和搜索問題。

我們推薦 第一個(gè)錯(cuò)誤的版本 這道題，作為介紹一個(gè)重要的算法的起始點(diǎn)。

88. 合并兩個(gè)有序數(shù)組

難度：簡單

給你兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，請(qǐng)你將 nums2 合并到 nums1 中，使 nums1 成為一個(gè)有序數(shù)組。

說明：

• 初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 。
• 你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素。

示例：

輸入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

輸出：[1,2,2,3,5,6]

提示：

• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1.length == m + n
• nums2.length == n

解題思路

• 合并兩個(gè)有序數(shù)組，這很簡單，你可以利用雙指針分別從兩個(gè)數(shù)組中取出較小的一個(gè)插入到新的數(shù)組中。

• 不過，本題中要求將給定的nums1數(shù)組作為結(jié)果的容器。

  同時(shí)，nums1后面填充了足夠的0來存放nums2中的元素。

• 我們是不是依然可以考慮雙指針的解法呢？

• 由于已知數(shù)組的真實(shí)長度，我們完全可以讓兩個(gè)指針分別指向兩個(gè)數(shù)組的隊(duì)尾，然后其中較大的那個(gè)必然是最終結(jié)果的最后一個(gè)元素，以此類推，我們可以從大到小填充完nums1。

方法一：雙指針

public void Merge(int[] nums1, int m, int[] nums2, int n)
{
    int p1 = m - 1;
    int p2 = n - 1;

    for (int i = nums1.Length - 1; p1 >= 0 && p2 >= 0; i--)
    {
        nums1[i] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
    }
    for (; p2 >= 0; p2--)
    {
        nums1[p2] = nums2[p2];
    }
}

278. 第一個(gè)錯(cuò)誤的版本

難度：簡單

你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開發(fā)的， 所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。

假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。

你可以通過調(diào)用 bool isBadVersion(version) 接口來判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)。 實(shí)現(xiàn)一個(gè)函數(shù)來查找第一個(gè)錯(cuò)誤的版本。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。

示例:

給定 n = 5，并且 version = 4 是第一個(gè)錯(cuò)誤的版本。

調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true
所以，4 是第一個(gè)錯(cuò)誤的版本。 

解題思路

• 樸素的想法是，對(duì)所有版本進(jìn)行線性掃描，當(dāng)找到第一個(gè)錯(cuò)誤的版本時(shí)，返回該版本即可。

  Func(n) => Range(1, n).First(x => IsBadVersion(x));
  

• 不過隨著版本數(shù)量的增加，我們很快就發(fā)現(xiàn)，這不是一個(gè)很好的解決問題的辦法。

• 稍加思考，對(duì)于版本號(hào)序列來說，本身其實(shí)也是有序的，第一出錯(cuò)版本之前的版本全部是正確的，而之后的版本全都是錯(cuò)誤的。

• 我們自然而然地就想到了二分查找的算法。

• 左指針左邊的版本全部是正確版本，右指針右邊的版本全部是錯(cuò)誤版本，每次我們都縮小了一個(gè)盡可能大的區(qū)間（當(dāng)前區(qū)間的一半）。

• 當(dāng)左指針超過右指針時(shí)，搜索結(jié)束，此時(shí)我們觀察兩個(gè)指針的位置，因?yàn)樽笾羔樧筮叺陌姹救渴钦_版本，我們很容易判斷出，第一個(gè)錯(cuò)誤的版本恰恰就是左指針當(dāng)前指向的版本。

方法一：二分查找

public int FirstBadVersion(int n) 
{
    return FindP(1, n);

    int FindP(int left, int right)
    {
        if(left > right) return left; // 遞歸的終點(diǎn)

        var mid = left + (right - left) / 2;

        return IsBadVersion(mid) ? FindP(left, mid - 1) : FindP(mid + 1, right);
    }
}