文章目錄
- 二分模板
- 整數二分
- 模板一
- 模板二
- 浮點數二分
- 寫出正確的二分
- 704. 二分查找
- 34.在排序陣列中查找元素的第一個和最后一個位置
- 69.X的平方根
- 33.搜索旋轉排序陣列
- 81.搜索旋轉排序陣列II
- 852.山脈陣列的峰頂索引
- 278.第一個錯誤的版本
這里的二分模板來源于 《演算法競賽進階指南》和Acwing，這里只是對模板的用法及Leetcode的例題講解， 同時歡迎各位加入Acwing社區
所謂二分演算法，就是不斷的縮減區間的范圍去尋找目標值
二分模板
整數二分
模板一
-
會將區間劃分為[l,mid] 和[mid+1,r]兩個區間，最終結果會落在左半區間
-
left指標和right指標最終都會落在相同的點上，可以通過兩個指標指向的值判斷是否是有解
int l = 0;
int r = nums.length-1;
while(l < r ){
int mid = l+r>>1;
if(check(mid)){
r = mid;
}else{
l = mid+1;
}
}
模板二
-
會將區間劃分為[l,mid-1] 和[mid,r]兩個區間，最終結果會落在右半區間
-
left指標和right指標最終都會落在相同的點上，可以通過兩個指標指向的值判斷是否是有解
int l = 0;
int r = nums.length-1;
while(ll < r){
int mid = l+r+1 >>1;
if(check(mid)){
l = mid;
}else{
r = mid-1;
}
}
浮點數二分
這個用的比較少，這里的k指的是題目的精度
double find(int left,int right){
double eps = le-k+2;
while(right - left > eps){
double mid = (right+left)/2;
if(check(mid)){
r = mid;
}else{
l = mid;
}
}
reutrn l;
}
寫出正確的二分
-
判斷題目是否可以使用二分，二分不僅僅適用于單調的序列，而且適用于有二段性的序列
-
通過判斷答案所落在的區間，以及mid 歸屬于那一半區間
-
寫出check函式，選用不同的模板
-
二分終止條件就是
l == r, 可以通過l或者是r指向的值是否是預期值，判斷有沒有解
704. 二分查找
題目描述
給定一個 n 個元素有序的（升序）整型陣列 nums 和一個目標值 target ，寫一個函式搜索 nums 中的 target，如果目標值存在回傳下標，否則回傳 -1
思路
這道題就是二分查找的模板題，
首先分析題目，這是一個有序的陣列，查找指定值，滿足二分的基本條件
這里是一個升序的陣列，如果說 num[mid] >= target,那么最終答案會落在左半區間，因為這又是一個升序的陣列，如果說mid指向的元素都比目標值大了，那么后面的只可能更大，
最終兩個指標都會指向同一個位置，可以通過判斷最后指向的位置是否為目標值，來判斷是否有解
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
while(l < r){
int mid = l+r >>1;
if(nums[mid]>= target){
r = mid;
}else{
l = mid+1;
}
}
if(nums[l] == target){
return l;
}
return -1;
}
}
34.在排序陣列中查找元素的第一個和最后一個位置
題目描述
該題同樣是可以用暴力解的，但是這里就不給出解法
在排序陣列中查找元素的第一個和最后一個位置
給定一個按照升序排列的整數陣列 nums，和一個目標值 target，找出給定目標值在陣列中的開始位置和結束位置，
如果陣列中不存在目標值 target，回傳 [-1, -1]，
思路
一般來說，看到有序的陣列，都要去想一想能不能用二分
-
如果說查找開始位置，在有解的情況之下，一定會落在候選區間的左半邊，所以說我們選擇
r = mid的這個模板，那么check函式就順理成章的寫出來了,nums[mid]>=target,這樣答案就會落在左半區間，那么就得到的就是開始位置 -
如果說查找結束位置，與分析開始位置是一致的，在有解的情況之下，一定會落在候選區間的右半邊，所以說我們選擇
l=mid的這個模板，那么check函式就是nums[mid]<=target,這樣答案就會落在右半區間，那么得到的就是結束位置
代碼
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = new int[]{-1,-1};
if(nums.length == 0){
return new int[]{-1,-1};
}
// >= target 中最小的那一個
int l = 0;
int r = nums.length-1;
while(l<r){
int mid = l+r>>1;
if(nums[mid]>=target){
r = mid;
}else{
l = mid+1;
}
}
if(nums[l] != target){
return ans;
}
// <= target 中最大的那一個
ans[0] = l;
l = 0;
r = nums.length-1;
while(l<r){
int mid = l+r+1>>1;
if(nums[mid]<=target){
l=mid;
}else{
r =mid-1;
}
}
if(nums[l]!=target){
return ans;
}
ans[1] =l;
return ans;
}
}
69.X的平方根
題目描述
給你一個非負整數 x ，計算并回傳 x 的 算術平方根 ，
由于回傳型別是整數，結果只保留 整數部分 ，小數部分將被 舍去 ，
注意：不允許使用任何內置指數函式和算符，例如 pow(x, 0.5) 或者 x ** 0.5 ，
思路
二分模板題
和上述兩個題都是同樣的分析方法
代碼
class Solution {
public int mySqrt(int x) {
long l = 0;
long r = x;
while(l<r){
long mid = l+r+1l>>1;
if(mid <= x/mid){
l = mid;
}else{
r = mid-1;
}
}
return (int)l;
}
}
33.搜索旋轉排序陣列
題目描述
整數陣列 nums 按升序排列，陣列中的值 互不相同 ，
在傳遞給函式之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉，使陣列變為[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標 從 0 開始 計數），例如， [0,1,2,4,5,6,7] 在下標 3 處經旋轉后可能變為 [4,5,6,7,0,1,2] ，
給你 旋轉后 的陣列 nums 和一個整數 target ，如果 nums 中存在這個目標值 target ，則回傳它的下標，否則回傳 -1 ，
示例 1：
輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4
思路
從題目中進行分析，陣列中沒有重復元素，原來的陣列升序的，旋轉之
后，我們很容易發現，前半段都是大于新陣列的第一個數，后半段都是小于新陣列的第一個數，仍然具有二段性，可以使用二分，那么說現在就用兩個問題，首先，就是如何去尋找這個分界點，其次，就是分界點確定之后，如果去運用我們的二分模板去尋找答案
-
分界點獲取
- 遍歷:分界點，后面的元素一定是比分界點出的元素小的
- 二分:整個序列具有二段性，前半段具有大于num[0] 的性質，后半段具有小于num[0]的性質
-
找到分界點之后，如果說target比第一個元素大，那么答案區間一定在多半段，反之，一定在右半段，不管是那一段，都是單調的，合理分析，既可以得到答案
代碼
class Solution {
public int search(int[] nums, int target) {
if(nums.length <= 0 ){
return -1;
}
int l = 0 ;
int r = nums.length-1;
while(l < r){
int mid = l+r+1>>1;
if(nums[mid]>=nums[0]) l = mid;
else r = mid-1;
}
if(target >= nums[0]) l = 0 ;
else{
l =r+1;
r = nums.length-1;
}
while(l < r){
int mid = l + r >> 1;
if(nums[mid]>=target){
r = mid;
}else{
l = mid +1;
}
}
if(nums[r] == target ){
return r;
}
return -1;
}
}
81.搜索旋轉排序陣列II
題目描述
已知存在一個按非降序排列的整數陣列 nums ，陣列中的值不必互不相同，
在傳遞給函式之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉 ，使陣列變為 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下標 從 0 開始 計數），例如， [0,1,2,4,4,4,5,6,6,7] 在下標 5 處經旋轉后可能變為 [4,5,6,6,7,0,1,2,4,4] ，
給你 旋轉后 的陣列 nums 和一個整數 target ，請你撰寫一個函式來判斷給定的目標值是否存在于陣列中，如果 nums 中存在這個目標值 target ，則回傳 true ，否則回傳 false ，
示例 1：
輸入：nums = [2,5,6,0,0,1,2], target = 0
輸出：true
思路
相比于上題，陣列中有了重復元素，使得不具有二段性，而沒有二段性的原因就是旋轉之后，新陣列的頭和尾中有了重復元素，如果說取出了這些重復元素，陣列就重新具有了二段性，如果說陣列尾和陣列頭是一致的，就壓縮陣列的右邊界，然后就和上題一樣的做法，之后就不在贅述
代碼一
直接遍歷，時間復雜度 O(n)
class Solution {
public boolean search(int[] nums, int target) {
for(int i = 0;i<nums.length;i++){
if(nums[i] == target){
return true;
}
}
return false;
}
}
代碼二
二分，最壞情況下是O(N),相比之下，更加推薦使用代碼一，代碼量更加短，時間復雜度一致
class Solution {
public boolean search(int[] nums, int target) {
if(nums.length == 0){
return false;
}
int R = nums.length - 1;
while(R >= 0 && nums[R] == nums[0] ){
R--;
}
if(R < 0) return nums[0] == target;
int r = R;
int l = 0;
while(l < r){
int mid = l+r+1 >> 1;
if(nums[mid] >= nums[0]) l = mid;
else r = mid-1;
}
if(target >= nums[0]){
r = l;
l = 0;
}else{
l++;
r = R;
}
while(l < r){
int mid = l+r>>1;
if(nums[mid]>=target) r = mid;
else l = mid+1;
}
if(nums[r] == target) return true;
return false;
}
}
852.山脈陣列的峰頂索引
題意描述
符合下列屬性的陣列 arr 稱為 山脈陣列 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1].
給你由整陣列成的山脈陣列 arr ，回傳任何滿足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]的下標 i ，
思路
這個陣列實際上是具有二段性，前面一段是單調遞增的，后面一段是單調遞減的，我們需要找到分界點下標，如果說當前元素，比他的前一個元素要大的話，說明答案會在右半邊
代碼
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 0;
int r = n-2;
while(l<r){
int mid = l+r+1>>1;
if(arr[mid]>arr[mid-1]){
l = mid;
}else{
r = mid-1;
}
}
return l;
}
}
278.第一個錯誤的版本
題目描述
你是產品經理，目前正在帶領一個團隊開發新的產品，不幸的是，你的產品的最新版本沒有通過質量檢測，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，
假設你有 n 個版本 [1, 2, …, n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，
你可以通過呼叫 bool isBadVersion(version) 介面來判斷版本號 version 是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，你應該盡量減少對呼叫 API 的次數
思路
- 從題意中分析，整個序列具有二段性，前面一段是沒有錯誤的版本，后面一段是錯誤的版本，所以可以用二分法去尋找中間的那個分割點
- 分析mid指標所指向的位置，如果說這個位置是錯誤的版本，那么答案最侄訓落至左半區間，選擇r = mid，的這個二分版本
- 只需要將題目中提供的函式作為check函式即可
- l == r 就是答案
代碼實作
時間復雜度 : O(logn)
空間復雜度 : O(l)
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l = 1;
int r = n;
while(l<r){
long tem =(long) l+r>>1;
int mid = (int)tem;
if(isBadVersion(mid)){
r = mid;
}else{
l = mid+1;
}
}
return l;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/336282.html
標籤：其他