一、前言

鏈表是數(shù)據(jù)結(jié)構(gòu)中重要的一個(gè)章節(jié)，他的重要性也不言而喻，在未來(lái)不管是筆試還是面試都會(huì)遇到這類的題目，所以接下來(lái)我就會(huì)把一些鏈表的常考的題目全部整理出來(lái)供大家學(xué)習(xí)指正。

二、刷題

<1>尋找峰值

題目鏈接

描述：

給定一個(gè)長(zhǎng)度為n的數(shù)組nums，請(qǐng)你找到峰值并返回其索引。數(shù)組可能包含多個(gè)峰值，在這種情況下，返回任何一個(gè)所在位置即可。
1.峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。嚴(yán)格大于即不能有等于
2.假設(shè) nums[-1] = nums[n] = ?∞
3.對(duì)于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的時(shí)間復(fù)雜度實(shí)現(xiàn)此問(wèn)題嗎？

數(shù)據(jù)范圍：

1≤nums.length≤2×10^5
?2 ^31<=nums[i]<=2 ^31?1

如輸入[2,4,1,2,7,8,4]時(shí)，會(huì)形成兩個(gè)山峰，一個(gè)是索引為1，峰值為4的山峰，另一個(gè)是索引為5，峰值為8的山峰，如下圖所示：

示例1

輸入：[2,4,1,2,7,8,4]
返回值：1
說(shuō)明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2

輸入：[1,2,3,1]
返回值：2
說(shuō)明：3 是峰值元素，返回其索引 2

思路分析：
這里用到了二分查找的性質(zhì)，因?yàn)閿?shù)組兩邊都是無(wú)窮小，所以我們只要往高處找就一定能找到波峰。那么我們就可以找一個(gè)元素，把數(shù)組分成兩個(gè)區(qū)間，每次就走高的一邊，最后就能鎖定出一個(gè)波峰。

int findPeakElement(int* nums, int numsLen ) {
    // write code here
    int left = 0, right = numsLen - 1;
    while(left < right)
    {
        int mid = (left + right) / 2;
        //右邊是往下，不一定有坡峰
        if(nums[mid] > nums[mid + 1])
        {
            right = mid;
        }  
        //右邊是往上，一定能找到波峰
        else
        {
            left = mid + 1;
        }
    }
    return left;
}

<2>二維數(shù)組中的查找

題目鏈接
描述：

在一個(gè)二維數(shù)組array中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
給定 target = 7，返回 true。
給定 target = 3，返回 false。

數(shù)據(jù)范圍：矩陣的長(zhǎng)寬滿足 0≤n，m≤500，矩陣中的值滿足0≤val≤10^9
進(jìn)階：空間復(fù)雜度 O(1)O(1) ，時(shí)間復(fù)雜度 O(n+m)O(n+m)

示例1

輸入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
說(shuō)明：存在7，返回true

示例2：

輸入：1,[[2]]
返回值：false

示例3

輸入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
說(shuō)明：不存在3，返回false

① 線性搜索

最簡(jiǎn)單的方法就是暴力遍歷，沒(méi)有用到二維數(shù)組的遞增性質(zhì)。
通過(guò)規(guī)律發(fā)現(xiàn)左下角所在元素的所在行最小，所在列最大，那么如果target小于所在元素，就讓行--，否則就讓列++。

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int row = arrayRowLen - 1, col = 0;
    while(row <= arrayRowLen - 1 && row >= 0 && col <= *arrayColLen - 1 && col >= 0)
    {
        if(array[row][col] == target)
        {
            return true;
        }
        else
        {
            if(array[row][col] < target)
            {
                col++;
            }
            else
            {
                row--;
            }
        }
    }
    return false;
}

② 逐行二分

因?yàn)槊恳恍卸际怯行蜻f增的，所以每一行都能用二分

bool binary_search(int* arr, int k, int target)
{
    int left = 0, right = k - 1;
    while (left <= right)
    {
        int mid = (right + left) / 2;
        if (arr[mid] == target)
        {
            return true;
        }
        else if (arr[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return false;
}



bool Find(int target, int** array, int arrayRowLen, int* arrayColLen) {
    // write code here
    for (int i = 0; i < arrayRowLen; i++)
    {
        if (binary_search(array[i], *arrayColLen, target))
        {
            return true;
        }
    }
   /*while (arrayRowLen--)
    {
        if (binary_search(*array, *arrayColLen, target))
        {
            return true;
        }
        array++;
    }*/
    return false;
}

<3>旋轉(zhuǎn)數(shù)組的最小數(shù)字

題目鏈接

描述：

有一個(gè)長(zhǎng)度為 n 的非降序數(shù)組，比如[1,2,3,4,5]，將它進(jìn)行旋轉(zhuǎn)，即把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，變成一個(gè)旋轉(zhuǎn)數(shù)組，比如變成了[3,4,5,1,2]，或者[4,5,1,2,3]這樣的。請(qǐng)問(wèn)，給定這樣一個(gè)旋轉(zhuǎn)數(shù)組，求數(shù)組中的最小值。

數(shù)據(jù)范圍：1≤n≤10000，數(shù)組中任意元素的值:0≤val≤10000
要求：空間復(fù)雜度：O(1)O(1) ，時(shí)間復(fù)雜度：O(logn)O(logn)

示例1:

輸入：[3,4,5,1,2]
返回值：1

示例2:

輸入：[3,100,200,3]
返回值：3

思路分析：
這道題其實(shí)是二分法的變形，旋轉(zhuǎn)點(diǎn)左邊的元素都單調(diào)遞增且都大于旋轉(zhuǎn)點(diǎn)右邊單調(diào)遞增的元素。
我們的目的是找到旋轉(zhuǎn)點(diǎn)也就是最小的元素，我們可以定義左left、右right指針讓他們相遇在旋轉(zhuǎn)點(diǎn)：
當(dāng)arr[mid] > arr[right]時(shí)
說(shuō)明mid一定在左遞增區(qū)間，為了使left移動(dòng)到旋轉(zhuǎn)點(diǎn)就需要縮小區(qū)間，left = mid + 1
當(dāng)arr[mid] < arr[right]時(shí)
說(shuō)明mid一定在右遞增區(qū)間，為了使right移動(dòng)到旋轉(zhuǎn)點(diǎn)就需要縮小區(qū)間，right = mid
但是也有相同元素的情況，例如：｛1，0，1，1，1｝
這樣就無(wú)法判斷mid在哪個(gè)區(qū)間了。
那么就讓right--，這里不能讓left++，因?yàn)槲覀兪歉钣疫叺脑乇容^,旋轉(zhuǎn)點(diǎn)一定在mid左邊。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-411818.html

int minNumberInRotateArray(int* arr, int sz ) {
    // write code here
    if(sz == 0)
    {
        return 0;
    }
    int left = 0, right = sz - 1;
    while(left < right)
    {
        int mid = (left + right) / 2;
        if(arr[mid] > arr[right])
        {
            left = mid + 1;
        }
        else if(arr[mid] < arr[right])
        {
            right = mid;
        }
        else
        {
            right--;
        }
    }
    return arr[left];
}

到了這里，關(guān)于【劍指Offer】二分法例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！