LeetCode 8題--Array+Binary search**

15611 ワード
LeetCode array search binary
この5つの問題はすべてarrayのbinary searchで解決できます
それぞれleetcode(35)——Search Insert Position leetcode(34)——Search for a Range leetcode(74)——Search a 2 D Matrix LeetCode(153)Find Minimm in Rotated Sorted Array LetCode(154)Find Minimum in Rotated Array II leetcode(33)——Search in Rotated Sorted Array letcode(81)——Search in Rotated Sorted Array II  LeetCode(162) Find Peak Element
一:leetcode(35)——Search Insert Position
タイトル:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples. [1,3,5,6],5→2 [1,3,5,6],2→1 [1,3,5,6],7→4 [1,3,5,6],0→0リンク:https://leetcode.com/problems/search-insert-position/
解析:解析により、midを直接返すことが見つかればいいことがわかりました.beginを返す必要があることが見つからないと、要求を満たします.検索対象の要素の下のラベルより大きい--begin**(1)
class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int begin = 0, end = n-1;
        int mid = 0;
        while(begin <= end){    //     +    
            mid = (begin+end)/2;
            if(A[mid] == target) return mid;
            else if(A[mid] < target) begin = mid+1;
            else end = mid-1;
        }
        return begin;
        
    }
};

二:leetcode(34)——Search for a Range
タイトル:
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return  [-1, -1] .
For example, Given  [5, 7, 7, 8, 8, 10]  and target value 8, return  [3, 4] .
リンク:https://leetcode.com/problems/search-for-a-range/
解析:この要素を二分検索で見つけた場合、直接戻るのではなく、beginとendがtargetに等しいかどうかを判断し、等しくなければbegin++とend--で****(2)に徐々に近づく.
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        int begin = 0, end = n-1;
        vector<int> result(2, -1);
        while(begin <= end){
            int mid = (begin+end)>>1;
            if( A[mid]== target){
                if(A[begin] == target && A[end] == target){  //                 target   
                    result[0]= begin;    
                    result[1] = end;
                    break;
                } 
                if(A[begin] != target) begin++;        //   begin++ end--    
                if(A[end] != target) end--;
                
            }else if(A[mid] < target) begin = mid+1;
            else end = mid-1;
        }
        return result;
    }
};

三:leetcode(74)——Search a 2 D Matrix
タイトル:
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix: 
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target =  3 , return  true . リンク:https://leetcode.com/problems/search-a-2d-matrix/
分析:この問題は2回の二分検索で、要素が存在する行を確定してから、行で二分検索を行えばいいです.
class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int m = matrix.size();
        if(m == 0) return false;
        int n = matrix[0].size();
        int begin = 0, end = m-1;
        int mid = 0;
        while(begin <= end){                //                   
            mid = (begin+end)/2;
            if(matrix[mid][0] == target) return true;
            else if(matrix[mid][0] < target) begin = mid+1;
            else end = mid-1;
        }
        
        int currentRow = 0;
        if(matrix[mid][0] > target) currentRow = mid -1;
        else currentRow = mid;
        if(currentRow < 0) return false;         
        begin = 0, end = n-1; 
        while(begin <= end){           //              
            mid = (begin + end)/2;
            if(matrix[currentRow][mid] == target) return true;
            else if(matrix[currentRow][mid] < target)begin = mid+1;
            else end = mid-1;
        }
        return false;
    }
};

四:leetcode(153)Find Minimum in Rotated Sorted Array
タイトル:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ).
Find the minimum element.
You may assume no duplicate exists in the array.
リンク:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
解析:この問題では,配列が秩序化されているかどうかにかかわらず,時間的複雑度がO(N)である従来の一般法の3つの方法を示した.第2の方法も同様であり,データの特徴からnum[0]よりも小さい要素を見つければよいし,時間的複雑度もO(N)である.第三の方法は二分検索であり、時間複雑度はO(lgN)である.
class Solution {
public:
    /*9ms   ：    */
    /*int findMin1(vector<int> &num) {
        int n = num.size();
        if(n == 0) return -1;
        int minMum = num[0];
        for(int i = 1; i < n; i++)
            minMum = min(num[i], minMum);
        return minMum;
    }*/
    
    /*  ：16ms*/
     /*int findMin(vector<int> &num) {
        int n = num.size();
        if(n == 0) return -1;
        if(num[0] <= num[n-1]) return num[0];
        
        int minMum = num[0];
        for(int i = 1; i < n; i++)
            if(num[i] < minMum) {
                minMum = num[i];
                break;
            }
        return minMum;
    }*/
    /*    ：6ms */
    int findMin(vector<int> &num) {
        int n = num.size();
        if(n == 0) return -1;
        if(num[0] <= num[n-1]) return num[0];
        int begin = 0, end = n-1;
        while(begin < end){
            int mid = (begin+end)/2;   //              
            if(num[mid] < num[begin]){
                if(mid > 0 && num[mid] < num[mid-1])
                    return num[mid];
                end = mid-1;
            }else{
                if(mid < end && num[mid] > num[mid+1])
                    return num[mid+1];
                begin = mid+1;
            }
        }
    }
    
    
};

内部に境界判定があるため、while(startint findMin(vector<int> &num){ int n = num.size(); if(n == 0) return -1; int s = 0, e = n-1; if(num[0] < num[e]) return num[0]; while(s < e-1){ // while int mid = (s + e)>>1; if(num[mid] < num[mid-1]) return num[mid]; if(num[mid] >= num[s]) s = mid+1; else e = mid-1; } return num[e]; }
五:leetcode(154)———Find Minimum in Rotated Sorted Array II
タイトル:
Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ).
Find the minimum element.
The array may contain duplicates.
リンク:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
分析:この問題は第4の問題の変形であり、要素が繰り返すことを意味する.このようにすれば、上述のアルゴリズムは、第1の要素と最後の要素が同時に、最小値がどこにあるかを判断できないという特殊な状況を処理する必要がある.解決策は、最後の要素とは異なる最初の値を見つけることから始まります(****4).
class Solution {
public:
    int findMin(vector<int> &num) {
        int n = num.size();
        if(n == 0) return -1;
        
        int i = 0;
        if(num[0] == num[n-1]){    //          22222212    212222222  num[mid]== num[begin]     
            for(i = 1; i < n; i++)    //     num[0] == num[n-1] ，        num[0]      
                if(num[i] != num[0])break;
        }
        if(i == n) return num[0];    //         
        if(num[i] < num[n-1]) return num[i];   //          
        
        int begin = i, end = n-1;
        while(begin < end){
            int mid = (begin+end)/2;   //              
            if(num[mid] < num[begin]){
                if(mid > 0 && num[mid] < num[mid-1])
                    return num[mid];
                end = mid-1;
            }else{
                if(mid < end && num[mid] > num[mid+1])
                    return num[mid+1];
                begin = mid+1;
            }
        }
    }
};

ここではdiscussの解法を提供し,4 msしか必要としない.
int findMin(int num[], int n) {

int mid,begin,end;
begin = 0;
end = n - 1;
while(begin <= end){
    mid = (begin + end) / 2;
    if(mid -1 >= 0 && num[mid] < num[mid - 1])
        return num[mid];
    else if(num[mid] > num[end])
        begin = mid + 1;
    else if(num[mid] < num[end])
        end = mid - 1;
    else
        end--;
}

return num[0];
}

六:leetcode(33)——Search in Rotated Sorted Array
タイトル:
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,  0 1 2 4 5 6 7  might become  4 5 6 7 0 1 2 ).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
リンク:https://leetcode.com/problems/search-in-rotated-sorted-array/
分析:ここでは2つの方法を提供します:法医は私たちが最小値O(N)時間を見つけて、それから最後の要素を通じて二分検索の区間を確定すればいいだけで、時間の複雑度はO(N)です.法二は直接二分検索であるが、判断は面倒で、誤りやすく、時間の複雑度はO(lgN)である.
法一:
class Solution {
public:
    int search(int A[], int n, int target) {
        if(n == 0) return -1;
        int minNum = A[0];
        int index = 0;
        for(int i = 1; i < n; i++){  //       
            if(A[i] < minNum){
                minNum = A[i];
                index = i;
            }
        }
        int begin = 0, end = n-1;      //        
        if(A[n-1] >= target)         //          
            begin = index;
        else
            end = index-1;
            
        while(begin <= end){
            int mid = (begin+end)/2;
            if(A[mid] == target) return mid;
            else if(A[mid] < target) begin = mid+1;
            else end = mid-1;
        }
        return -1;
        
    }
};

法二:
class Solution {
public:   
    int search(int A[], int n, int target) {
        if(n == 0) return -1;
        int begin = 0, end = n-1;
        while(begin <= end){
            int mid = (begin + end) >> 1;
            if(A[mid] == target) return mid;
            if(A[mid] < A[begin]){     //        
                if(A[mid] > target || target >= A[begin]) end = mid-1;  
                else begin = mid+1;
            }else{
                if(A[mid] < target || target < A[begin]) begin = mid+1;
                else end = mid-1;
            }
            
        }
        return -1;
    }
};

ここで後半の判断はA[mid]とA[begin]で大きさを比較するのがはっきりしているので、A[mid]とtargetの方法で判断してもいいので、面倒です.実は逆で、上下ともに同じで、判断しながらOK..
int rotationArray(int *arr, int n, int target){
	int s = 0, e = n-1;
	while(s <= e){
		int mid = (s+e) >> 1;
		if(arr[mid] == target) return mid;
		else if(target > arr[mid]){
			if(arr[mid] >= arr[s] || target < arr[s]) s= mid+1;
			else e = mid -1;
		}
		else{
			if(arr[mid] < arr[s] ||  target >= arr[s]) e= mid-1;
			else s = mid+1;
		
		}
	
	}
	return -1;
}

七:leetcode(81)——Search in Rotated Sorted Array II
タイトル:
Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
リンク:https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
分析:法一:ここでは要素を繰り返すことが要求されているので、最大値に近い最小を見つける必要があります.他の考えは問題とそっくりです.法二も二分検索ですが、第五題と同様に、前の問題を改善し、前と尾の同じ要素を除去する必要があります.
法一:
class Solution {
public:
    bool search(int A[], int n, int target) {
        if(n == 0) return false;
        int minNum = A[0];
        int index = 0;
        for(int i = 1; i < n; i++){  //       
            if(A[i] <= minNum && A[i-1] > A[i]){         //                  
                minNum = A[i];
                index = i;
            }
        }
        int begin = 0, end = n-1;      //   A[n-1]       
        if(A[n-1] >= target)         //          
            begin = index;
        else
            end = index-1;
            
        while(begin <= end){
            int mid = (begin+end)/2;
            if(A[mid] == target) return true;
            else if(A[mid] < target) begin = mid+1;
            else end = mid-1;
        }
        return false;
    }
};

法二:
class Solution {
public:    
     bool search(int A[], int n, int target) {
        if(n == 0) return false;
        int i = 0;
        if(A[0] == target) return true;
         if(A[0] == A[n-1]){    //                       ，       
            for(i = 1; i < n; i++)    
                if(A[i] != A[0])break;
        }
        int begin = i, end = n-1;
        while(begin <= end){
            int mid = (begin + end) >> 1;
            if(A[mid] == target) return true;
            if(A[mid] < A[begin]){
                if(A[mid] > target || target >= A[begin]) end = mid-1;    //     
                else begin = mid+1;
            }else{
                if(A[mid] < target || target < A[begin]) begin = mid+1;
                else end = mid-1;
            }
            
        }
        return false;
        
    }
};

八:leetcode(162)Find Peak Element
タイトル:
A peak element is an element that is greater than its neighbors.
Given an input array where  num[i] ≠ num[i+1] , find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that  num[-1] = num[n] = -∞ .
For example, in array  [1, 2, 3, 1] , 3 is a peak element and your function should return the index number 2. リンク:https://leetcode.com/problems/find-peak-element/
分析:この問題の鍵は要素の分布状況にあり、分布状況を理解すれば二分で検索する方法がわかる.なぜならnum[-1] = num[n] = -∞.したがってnum[mid]の一方num[mid-1]またはnum[mid+1]にnum[mid]より大きいものがある場合、より大きい方にはpeak elementが必ず存在するのでlogn時間内に完了することができる
class Solution {
public:
    /*int findPeakElement(const vector<int> &num) {
        int n = num.size();
        if(n <= 1) return 0;
        
        for(int i = 1; i < n-1; i++){
            if(num[i]> num[i-1] && num[i] > num[i+1])return i;
        }
        if(num[n-1] > num[n-2]) return n-1;
        return 0;
        
    }*/
    int findPeakElement(const vector<int> &num) {
        int start = 0, end = num.size()-1;
        while(start < end-1){
            int mid = (start+end) >> 1;
            if(num[mid] > num[mid+1] && num[mid] > num[mid-1]) return mid;
            else if(num[mid] > num[mid+1]) end = mid-1;
            else start = mid+1;
        }
        return num[start] < num[end]? end:start;
    }
};

注意while(start
Spring学習(五)——ユーティリティ
!importantの使い方