暑期算法訓練.5

20. 力扣 34.在排序數組中查找元素的第一個位置和最后一個位置

20.1 題目解析：

20.2 算法思路：

20.3 代碼演示：

?編輯

20.4 總結反思：

21.力扣 69.x的平方根?

21.1 題目解析：

21.2 算法思路：

21.3 代碼演示：

21.4 總結反思：

22. 力扣 35.搜索插入位置

22.1 題目解析：

22.2 算法思路：

22.3 代碼演示：

?編輯

22.4 總結反思：

23 力扣. 852 山脈數組的封頂索引

23.1 題目解析：

23.2 算法思路：

23.3 代碼演示：

23.4 總結反思：

24.力扣 162 尋找峰值：

24.1 題目解析：

?編輯?

24.2 算法思路：

24.3 代碼演示：

24.4 總結反思：

25.力扣 LCR 173 點名

25.1 題目解析：

25.2 算法思路:

25.3 代碼演示：

?編輯

25.4 總結反思：

26 力扣 153.尋找旋轉排序數組中的最小值

26.1 題目解析：

26.2 算法思路：

26.3 代碼演示：

?編輯

26.4 總結反思：

20. 力扣 34.在排序數組中查找元素的第一個位置和最后一個位置

20.1 題目解析：

題目很好理解，就是讓你找出目標值的開始以及結束的位置。不過這道題目要注意處理一下，空數組以及沒有結果的情況。

20.2 算法思路：

1.解法一就是暴力解法，就是遍歷一遍數組，然后找出區間即可。這個的時間復雜度肯定是O（N）

2.解法二是咱們今天重點講解的，就是用二分算法去解決這道題目。咱們直到，要想用二分算法，得先關注一下這道題目，得具有二段性才可以使用二分算法。?升不升序倒是無所謂。因為你只要發現了規律，均可以使用二分算法。

【1】求區間左端點

【2】求區間右端點

總結一下就是：

好了，這個題目的算法思路可算是寫明白了。

20.3 代碼演示：

vector<int> searchRange(vector<int>& nums, int target) {if (nums.size() == 0)  return { -1,-1 };//處理一下數組為空的情況int begin = 0;int left = 0; int right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target) left = mid + 1;else right = mid;}//判斷一下是否有結果，因為出了while循環后，left==rightif (nums[left] != target) return { -1,-1 };else begin = left;//這里寫begin的目的僅僅是為了將left給存起來left = 0; right = nums.size() - 1;//其實，left直接從左端點開始就可以了while (left < right){int mid = left + (right - left + 1) / 2;if (nums[mid] <= target) left = mid;else right = mid - 1;}return { begin,right };//此時不需要判斷是否有結果，因為只要有左端點，那么就一定有結果
}
int main()
{vector<int> nums = { 5,7,7,8,8,10 };int target = 8;vector<int> outcome = searchRange(nums, target);for (auto& e : outcome){cout << e << "";}cout << endl;return 0;
}

20.4 總結反思：

咱們來總結一下這類二分的模板：

不用死記硬背，只需要記住一點：就是若是下面出現了-1，那么上面mid給它加上1就可以了。

記住了求中點的方式，就可以推導出其他的了。

21.力扣 69.x的平方根?

21.1 題目解析：

21.2 算法思路：

暴力解法很簡單，就是遍歷一邊【0，x】內的數字i，若?i*i=x，直接返回x。若是i*i>x,則返回上一個數即可。

下面看解法二：

注意：尋找區間左端點，即找到大于等于目標值，說明右邊還有滿足條件的目標值（第一個滿足條件的元素）。

尋找區間右端點：即找到小于等于目標值，說明右邊不可能還有滿足條件的目標值。（最后一個滿足條件的元素）

所以說，為什么說這個尋找左端點是： <? ? ? ?>=.原理上將等于歸于右邊，是因為若mid位于兩個相等的值中間，此時不是最終結果。但你也可以想成，就是找左端點，右邊肯定還有值。所以找右端點：左邊還有值，就是<=? ? ? ?>

所以本題是尋找k*k<=x,尋找右端點模板。

21.3 代碼演示：

int mySqrt(int x) {if (x < 1)  return 0;//處理邊界情況int left = 0;long long right = x;while (left < right){long long mid = left + (right - left + 1) / 2;//long long 防止溢出if (mid * mid <= x)  left = mid;else right = mid - 1;}return left;
}
int main()
{int x = 4;cout << mySqrt(x) << endl;return 0;
}

21.4 總結反思：

這個起始也就是一種二分算法的模板而已。

22. 力扣 35.搜索插入位置

22.1 題目解析：

注意關鍵句子：有序數組找到一個值。

22.2 算法思路：

1.找到了：直接返回下標即可。

2.若是沒找到，就第一次出現了比目標值大的那個數（那個數大于等于目標值target）。或者數組末尾。

這個mid（x）其實就是“那個數”，然后再繼續進行判斷即可。

22.3 代碼演示：

int searchInsert(vector<int>& nums, int target) {int left = 0; int right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)  left = mid + 1;else right = mid;}if (nums[left] < target) return left + 1;//處理一下邊界的情況，就是插入到數組末尾return left;
}
int main()
{vector<int> nums = { 1,3,5,6 };int target = 5;cout << searchInsert(nums, target) << endl;return 0;
}

22.4 總結反思：

這道題目是用到了求左端點的模板。要注意分清楚，還是挺好抓住的。

23 力扣. 852 山脈數組的封頂索引

23.1 題目解析：

就是讓你找出山頂的索引。

23.2 算法思路：

就是找出最大的值唄。

1.暴力解法也好辦，即使先遍歷一遍數組，直至找到后一個數字比前一個數字小為止。返回那個數字的下標就可以了。

2.解法二就是二分查找算法：

那么這個時候：1.arr[mid]>arr[mid-1]（說明要到右區間去找），left=mid

? ? ? ? ? ? ? ? ? ? ? ? ? 2.arr[mid]<arr[mid-1]（說明要到左區間去找），即right=mid-1

mid位置呈現上升：那么接下來要在[mid+1,right]區間內搜索山峰。

mid位置呈現下降趨勢，在[left,mid-1]區間內搜索山峰。

mid位置就是山峰，那么直接返回即可。

23.3 代碼演示：

int peakIndexInMountainArray(vector<int>& arr) {int left = 0; int right = arr.size();while (left < right){int mid = left + (right - left + 1) / 2;if (arr[mid] > arr[mid - 1])  left = mid;else right = mid - 1;}return left;
}
int main()
{vector<int> arr = { 0,1,0 };cout << peakIndexInMountainArray(arr) << endl;return 0;
}

23.4 總結反思：

這道題目就不可以傻乎乎的再硬用了，需要分析一下為什么使用二分算法了。

24.力扣 162 尋找峰值：

24.1 題目解析：

?

上一道題目是只有一個峰，但這個是有好多個峰，但是只返回任意一個峰即可。

并且題目中要求左，右，都可以是無窮小。

24.2 算法思路：

暴力解法：就是從第一個位置開始，一直向后走，分情況討論：

1.一開始就下降。2，上升著突然就下降了。3? 一直向上走到最后一個位置。

2.二分算法：

這個mid應該就是隨機選取的地方，然后再由這個分析規律（一開始，mid可能不等于你要求的那個值，只要是一個隨機的值，但是循環完了，之后呢？left=right，此時的mid即為所求的值了。）

且上面所說的模板，若你right=mid-1，看到了減去一，那么在前面加上一就可以了。?

24.3 代碼演示：

int findPeakElement(vector<int>& nums) {int left = 0; int right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]) right = mid;else left = mid + 1;}return left;
}int main()
{vector<int> nums = { 1,2,3,1 };cout << findPeakElement(nums) << endl;return 0;
}

24.4 總結反思：

這道題目也是考你靈活的運用二分模板。

25.力扣 LCR 173 點名

25.1 題目解析：

?這道題目就是讓你找出缺失的數字

25.2 算法思路:

其實這道題目解法有很多，但是咱們今天在這里只講二分算法：

這個3就是區間的左端點。

1.左區間：若nums[mid]==mid,則left=mid+1；

2.右區間：nums[mid]!=mid,則right=mid

細節問題：邊界：[0 ,1 ,2 ,3 ] 那么它缺的就是4.但是二分算法尋找的是右區間。但是這里沒有右區間。所以，若最后一個值與下標值相同，則為完全遞增數組，則返回left+1即可。

25.3 代碼演示：

//點名
int takeAttendance(vector<int>& records) {int left = 0; int right = records.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (records[mid] == mid)  left = mid + 1;else right = mid;}if (left == records[left]) return left + 1;else return left;
}
int main()
{vector<int> records = { 0,1,2,3,5 };cout << takeAttendance(records) << endl;return 0;
}

25.4 總結反思：

這道題目也是一道令人有想法的二分算法。?

26 力扣 153.尋找旋轉排序數組中的最小值

26.1 題目解析：

這道題目是我做的二分算法題目里面最不好理解的，也是最不好想的。題目很簡單。咱們接下來看怎么做

26.2 算法思路：

咱們只講二分算法：

好，這個是以D點為參照點。那么以A點為參照點呢？

26.3 代碼演示：

以D點為參照點：

//尋找旋轉排序數組中的最小值
//以D點為參照點
int findMin(vector<int>& nums)
{int left = 0, right = nums.size() - 1;int x = nums[right]; // 標記?下最后?個位置的值(D點）while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > x) left = mid + 1;else right = mid;}return nums[left];
}
int main()
{vector<int> nums1 = { 4,5,6,7,0,1,2 };vector<int> nums2 = { 3,4,5,1,2 };vector<int> nums3 = { 11,13,15,17 };cout << "nums1的最小值: " << findMin(nums1) << endl; // 輸出0cout << "nums2的最小值: " << findMin(nums2) << endl; // 輸出1cout << "nums3的最小值: " << findMin(nums3) << endl; // 輸出11return 0;
}

以A點為參照點：

//以A點為參照點
int findMin(vector<int>& nums) {int left = 0;                  // A點，左邊界int right = nums.size() - 1;// 數組未旋轉的情況（完全升序）if (nums[left] <= nums[right]) {return nums[left];}// 二分查找while (left < right) {int mid = left + (right - left) / 2;// 中間元素大于左邊界元素，說明左半部分有序，最小元素在右半部分if (nums[mid] > nums[left]) {left = mid;}// 中間元素小于左邊界元素，說明最小元素在左半部分（包括mid）else {right = mid;}}// 循環結束時left == right，此時下一個元素即為最小值return nums[left + 1];
}
int main()
{vector<int> nums1 = { 4,5,6,7,0,1,2 };vector<int> nums2 = { 3,4,5,1,2 };vector<int> nums3 = { 11,13,15,17 };cout << "nums1的最小值: " << findMin(nums1) << endl; // 輸出0cout << "nums2的最小值: " << findMin(nums2) << endl; // 輸出1cout << "nums3的最小值: " << findMin(nums3) << endl; // 輸出11return 0;
}