[数据结构与算法]leetcode 算法基础day1

1.

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回?[-1, -1]。

你必须设计并实现时间复杂度为?O(log n)?的算法解决此问题。

题解:

注意nums是升序排列的。要求使用时间复杂度为O(log n)的算法，所以不能采用从头到尾遍历数组的方式（O(n)）。二分查找的时间复杂度为O(log n)。

class Solution {
    public int[] searchRange(int[] nums, int target) {
    if(nums.length == 0) return new int[]{-1,-1};

    int l=0,r=nums.length-1;    //第一次二分查找范围
    while(l<r){     //寻找左边界
        int mid = (l + r)/2;  //相当于向下取整，为寻找左边界
        if(nums[mid]>=target) r=mid;
        else l = mid + 1;
    }
    if(nums[r]!= target) return new int[]{-1,-1};
    int L = r;    //L为查询结果左边界
    l = 0; r = nums.length - 1;    //第2次二分查找范围 
    while(l < r){    //寻找右边界
    int mid = (l+r+1)/2;   //相当于向上取整，为寻找右边界
    if(nums[mid] <= target) l = mid;
    else r= mid-1;
    }
    return new int[]{L,r};
}
}

binaryseasrch：使用binarySearch方法检索（二分法）的前提是要对集合内数据进行排序

关于new int[]：代码中只写int[] num 时，表示声明了一个int型的数组，但是这个数组还未分配空间，不能使用。如果要使用这个数组的话，就需要为这个数组分配空间，即num = new int[数组长度]，这样的话这个数组就能够正常使用了。

Java中两个整数相除,如果不能整除,默认是向下取整的。

确定左右边界关键：等号是和大于在一起还是小于在一起，以左边界举例的话就是每次边界收缩时 l指针mid+1左侧的mid一定是小于target的，这就保证了循环结束时 L指针的左侧必定和自己相异

2.

整数数组 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?。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

题解：

nums升序排列！有序数组使用二分查找岂不美哉。但是原升序数组进行了旋转，使得原来的有序变成了局部有序。?

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环。

class Solution {
public:
    int search(vector<int>& nums, int target) {
    int l=0,r=nums.size()-1;
    while(l<=r){
        int mid =(r+l)>>1;
        if(nums[mid]==target) return mid;
        if(nums[mid]>=nums[l]){
            if(target>=nums[l] && target<nums[mid]) r=mid-1;
            else l=mid+1;
        }
        else{
            if(target>nums[mid]&&target<=nums[r]) l=mid+1;
            else r=mid-1;
        }
        
    }
    return -1;
    }
};

3.

编写一个高效的算法来判断?m x n?矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

题解：

若将矩阵的每一行拼接到上一行结尾，就构成一个升序数组！有序数组直接二分查找嘛！

在实现时，要将二分升序的数组下标映射到原矩阵的行和列上。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
    int m=matrix.length,n=matrix[0].length;//m行n列
    int low=0,high=m*n-1;
    while(low<=high){
        int mid=(low+high)/2; //二分有序数组的mid下标
        int x = matrix[mid/n][mid%n];//mid映射到原矩阵的下标
        //剩下的就是绝活二分查找啦
        if(x<target){
            low=mid+1;
        }else if(x>target){
            high=mid-1;
        }else{
            return true;
        }
    
    }
    
    return false;
    }
    
}