力扣初級演算法（五）【排序和搜索】

本文中的題目均來自力扣，代碼默認以C#實作，偽代碼僅用來幫助描述，不嚴格遵循某種語言的語法，

本章涵蓋了在有序結構中的排序和搜索問題，

我們推薦第一個錯誤的版本這道題，作為介紹一個重要的演算法的起始點，

力扣初級演算法（五）【排序和搜索】
- 88. 合并兩個有序陣列
  - 解題思路
    - 方法一：雙指標
- 278. 第一個錯誤的版本
  - 解題思路
    - 方法一：二分查找

88. 合并兩個有序陣列

難度：簡單

給你兩個有序整數陣列 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序陣列，

說明：

初始化 nums1 和 nums2 的元素數量分別為 m 和 n ，

你可以假設 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

解題思路

合并兩個有序陣列，這很簡單，你可以利用雙指標分別從兩個陣列中取出較小的一個插入到新的陣列中，
不過，本題中要求將給定的nums1陣列作為結果的容器，

同時，nums1后面填充了足夠的0來存放nums2中的元素，
我們是不是依然可以考慮雙指標的解法呢？
由于已知陣列的真實長度，我們完全可以讓兩個指標分別指向兩個陣列的隊尾，然后其中較大的那個必然是最終結果的最后一個元素，以此類推，我們可以從大到小填充完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. 第一個錯誤的版本

難度：簡單

你是產品經理，目前正在帶領一個團隊開發新的產品，不幸的是，你的產品的最新版本沒有通過質量檢測，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，

假設你有 n 個版本 [1, 2, ..., n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，

你可以通過呼叫 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，你應該盡量減少對呼叫 API 的次數，

示例:
給定 n = 5，并且 version = 4 是第一個錯誤的版本，

呼叫 isBadVersion(3) -> false
呼叫 isBadVersion(5) -> true
呼叫 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本， 

解題思路

樸素的想法是，對所有版本進行線性掃描，當找到第一個錯誤的版本時，回傳該版本即可，
```
Func(n) => Range(1, n).First(x => IsBadVersion(x));
```
不過隨著版本數量的增加，我們很快就發現，這不是一個很好的解決問題的辦法，
稍加思考，對于版本號序列來說，本身其實也是有序的，第一出錯版本之前的版本全部是正確的，而之后的版本全都是錯誤的，
我們自然而然地就想到了二分查找的演算法，
左指標左邊的版本全部是正確版本，右指標右邊的版本全部是錯誤版本，每次我們都縮小了一個盡可能大的區間（當前區間的一半），
當左指標超過右指標時，搜索結束，此時我們觀察兩個指標的位置，因為左指標左邊的版本全部是正確版本，我們很容易判斷出，第一個錯誤的版本恰恰就是左指標當前指向的版本，

方法一：二分查找

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

    int FindP(int left, int right)
    {
        if(left > right) return left; // 遞回的終點

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

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/180918.html

標籤：其他

上一篇：兩個鏈表的第一個公共結點

下一篇：10.18號題解報告