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

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

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

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

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

難度：簡(jiǎn)單

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

說(shuō)明：

• 初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 。
• 你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來(lái)保存 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ù)組，這很簡(jiǎn)單,，你可以利用雙指針?lè)謩e從兩個(gè)數(shù)組中取出較小的一個(gè)插入到新的數(shù)組中,。

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

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

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

• 由于已知數(shù)組的真實(shí)長(zhǎng)度,，我們完全可以讓兩個(gè)指針?lè)謩e指向兩個(gè)數(shù)組的隊(duì)尾，然后其中較大的那個(gè)必然是最終結(jié)果的最后一個(gè)元素,，以此類(lèi)推,，我們可以從大到小填充完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ò)誤的版本

難度：簡(jiǎn)單

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

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

你可以通過(guò)調(diào)用 bool isBadVersion(version) 接口來(lái)判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)。 實(shí)現(xiàn)一個(gè)函數(shù)來(lái)查找第一個(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)行線性?huà)呙?，?dāng)找到第一個(gè)錯(cuò)誤的版本時(shí),，返回該版本即可。

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

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

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

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

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

• 當(dāng)左指針超過(guò)右指針時(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);
    }
}