Day03——数组专题

╰+哭是因爲堅強的太久メ 2024-04-03 10:29 88阅读 0赞

#### 文章目录 ####

*   *   *  6.搜索插入位置：
         *  二分法：
         *  7.在排序数组中查找元素的第一个和最后一个位置：
         *  寻找右边界
         *  寻找左边界
         *  处理三种情况

--------------------

#### 6.搜索插入位置： ####

**思路：**

*  目标值在数组所有元素之前
 *  目标值等于数组中某一个元素
 *  目标值插入数组中的位置
 *  目标值在数组所有元素之后

#### 二分法： ####

1.看到题里给出的数组是有序数组，都可以想一想是否可以使用**二分法**。

**代码实现：**

class Solution {
        
        public int searchInsert(int[] nums, int target) {
        
            int n = nums.length;
            
            // 定义target在左闭右闭的区间，[low, high]
            int low = 0;
            int high = n - 1;
    
            while (low <= high) {
         // 当low==high，区间[low, high]依然有效
                int mid = low + (high - low) / 2; // 防止溢出
                if (nums[mid] > target) {
        
                    high = mid - 1; // target 在左区间，所以[low, mid - 1]
                } else if (nums[mid] < target) {
        
                    low = mid + 1; // target 在右区间，所以[mid + 1, high]
                } else {
        
                    // 1. 目标值等于数组中某一个元素  return mid;
                    return mid;
                }
            }
            // 2.目标值在数组所有元素之前 3.目标值插入数组中 4.目标值在数组所有元素之后 return right + 1;
            return high + 1;
        }
    }

#### 7.在排序数组中查找元素的第一个和最后一个位置： ####

寻找target在数组里的左右边界，有如下三种情况：

*  情况一：target 在数组范围的右边或者左边，例如数组\{3, 4, 5\}，target为1或者数组\{3, 4, 5\},target为9，此时应该返回\{-1, -1\}
 *  情况二：target 在数组范围中，且数组中不存在target，例如数组\{3,5,7\},target为4，此时应该返回\{-1, -1\}
 *  情况三：target 在数组范围中，且数组中存在target，例如数组\{3,6,7\},target为6，此时应该返回\{1, 1\}

#### 寻找右边界 ####

int getRightBorder(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
            while (left <= right) {
                int middle = left + ((right - left) / 2);
                if (nums[middle] > target) {
                    right = middle - 1;
                } else { // 寻找右边界，nums[middle] == target的时候更新left
                    left = middle + 1;
                    rightBorder = left;
                }
            }
            return rightBorder;
        }

#### 寻找左边界 ####

int getLeftBorder(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
            while (left <= right) {
        
                int middle = left + ((right - left) / 2);
                if (nums[middle] >= target) {
         // 寻找左边界，nums[middle] == target的时候更新right
                    right = middle - 1;
                    leftBorder = right;
                } else {
        
                    left = middle + 1;
                }
            }
            return leftBorder;
        }

#### 处理三种情况 ####

class Solution {
        
        int[] searchRange(int[] nums, int target) {
        
            int leftBorder = getLeftBorder(nums, target);
            int rightBorder = getRightBorder(nums, target);
            // 情况一
            if (leftBorder == -2 || rightBorder == -2) return new int[]{
        -1, -1};
            // 情况三
            if (rightBorder - leftBorder > 1) return new int[]{
        leftBorder + 1, rightBorder - 1};
            // 情况二
            return new int[]{
        -1, -1};
        }
    
        int getRightBorder(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
            while (left <= right) {
        
                int middle = left + ((right - left) / 2);
                if (nums[middle] > target) {
        
                    right = middle - 1;
                } else {
         // 寻找右边界，nums[middle] == target的时候更新left
                    left = middle + 1;
                    rightBorder = left;
                }
            }
            return rightBorder;
        }
    
        int getLeftBorder(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
            while (left <= right) {
        
                int middle = left + ((right - left) / 2);
                if (nums[middle] >= target) {
         // 寻找左边界，nums[middle] == target的时候更新right
                    right = middle - 1;
                    leftBorder = right;
                } else {
        
                    left = middle + 1;
                }
            }
            return leftBorder;
        }
    }