代码面试之数组小结（还未更新完）

数组

数组的特点：连续内存、相同数据类型、随机索引、线性表

✔ [704]二分查找 54.3% Easy 0.0%（理论题：特别注意区间定义！）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的
target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4

数组二分法解题有两种区间定义，绝对不能混淆。

左闭右开

class Solution {
    public int search(int[] nums, int target) {
        int left = 0; // 左侧初始边界为0
        int right = nums.length; // 右侧初始边界为数组长度！！
        // 此时区间是[left, right)
        while(left < right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // [left, middle)
            } else if (nums[middle] < target) {
                left = middle + 1; // [middle + 1, right)
            } else {
                return middle;
            }
        }
        // 没找到目标值
        return -1;
    }
}

左闭右闭

class Solution {
    public int search(int[] nums, int target) {
        int left = 0; // 左侧初始边界为0
        int right = nums.length - 1; // 右侧初始边界为右侧索引！！！
        // 此时区间定义是[left, right]
        while (left <= right) { // 因为是闭合区间，left仍然可以等于right
            int middle = left + (right - left) / 2;
            if (nums[middle] > target) { // 中间值大于target
                right = middle - 1; // [left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // [middle + 1, right]
            } else {
                return middle;
            }
        }
        // 没找到目标值
        return -1;
    }
}

✔ [35]搜索插入位置 45.4% Easy 0.0%（通过率低，区间定义容易搞错！！！）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。

如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2:

输入: nums = [1,3,5,6], target = 2 输出: 1 示例 3:

输入: nums = [1,3,5,6], target = 7 输出: 4

本题首先搞清楚插入的位置，有四种情况：

1. 插入在左侧 [0, -1]放到0位置
2. 插入在某个数值位置 正好是middle位置
3. 插入在某个数值后
4. 插入在数组后

用了二分法时间o(logn)，空间o(1)

class Solution {
    // 左闭右闭 区间定义
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + ((right - left) >> 1);
            if (target < nums[middle]) {
                right = middle - 1;
            } else if (target > nums[middle]) {
                left = middle + 1;
            } else { 
                return middle;
            }
        }
        return right + 1;
    }
}

本题也可以用暴力法，遍历一次数组即可o(n)。

✔ [34]在排序数组中查找元素的第一个和最后一个位置 42.2% Medium 0.0%（重点备注）

给定一个按照升序排列的整数数组 nums，和一个目标值 target。

找出给定目标值在数组中的开始位置和结束位置。

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

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1：

输入：nums = [ 5,7,7,8,8,10] , target = 8 输出：[3,4] 示例 2：

输入：nums = [ 5,7,7,8,8,10] , target = 6 输出：[-1,-1] 示例 3：

输入：nums = [], target = 0 输出：[-1,-1] 提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109 nums 是一个非递减数组
-109 <= target <= 109

水平太次了，这道题做了好久好久。

最后还是看了大佬的答案做完的。

有序的数组第一眼想到二分法，但是可能有重复元素，所以中间值正好等于target值的时候就不好判断。

大佬给出的方法是分别求解左右两个边界。

感觉跟大佬的思维方式不太一样，慢慢学习了。

。

数组问题首先分析边界，本题有多种边界：
1. target在数组左右两侧
2. target在数组内，等于某个值
3. target在数组内，不等于某个值。

定义规则：分别找出右侧和左侧的边界，边界不包含target值。

• 按照定义的规则，如果等于某个值时，分别取到不包含这个值的边界，这样左右边界至少隔着1个target；
• 左边界通过右侧一点一点推，右侧边界通过左侧一点点推。
  

  
  

  
  就写到这了，也没完全贯通。
  

  
  

  。
  

  
  

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 分别寻找出左右边界，边界不包含target值
        int left = leftBorder(nums, target);
        int right = rightBorder(nums, target);
        // 在数组左右两侧。

只有中间值一直大于或者小于目标值才会出现下面结果
        if (left == -2 || right == -2) {
            return new int[]{-1, -1};
        }
        // 如果数组存在target值，因为边界不包含target，就会出现 left - target - right的情况
        if (right - left > 1) {
            return new int[]{left + 1, right - 1};
        }
        //
        return new int[]{-1, -1};
    }

    // 找到右侧边界，不包含target的边界
    private int rightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 仅用于标记右侧边界
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] > target) { // 中间值较大时，target在左侧
                right = middle - 1; // 此时右侧target在[left, middle-1]范围内
            } else { // 中间值小于或者等于target，说明target在右侧
                left = middle + 1; //
                rightBorder = left; // 从左往右找边界
            }
        }
        return rightBorder;
    }

    // 找到左侧边界，不包含target的边界
    private int leftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 标记左边界
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] < target) {
                left = middle + 1; // 此时target在右侧，[middle+1, right]
            } else { // 中间值在左侧
                right = middle - 1;
                leftBorder = right; // 从右到左推移边界
            }
        }
        return leftBorder;
    }
}

✔ [69]x 的平方根 38.9% Easy 0.0%

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4 输出：2 示例 2：

输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 231 - 1

解题思路仍然是二分法。

本题中使用左闭右闭区间定义，并保持定义不变。

使用一个变量res暂时记录结果。

一个很大的优点是，使理解没有那么绕，很多题解中，需要对加1减1做很多思考。

class Solution {
    public int mySqrt(int x) {
        // 0或1时，算术平方根就是本身
        if (x == 1 || x == 0) {
            return x;
        }
        // 二分法 使用左闭右闭
        int left = 1;
        int right = x; // 输入值：8
        int res = -1; // 记录结果
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (middle > x / middle) { // 避免直接相乘溢出。


                right = middle - 1;
            } else if (middle < x / middle) {
                res = middle; // 暂时记录middle值，因为left+1后平方不一定满足小于x了。


                left = middle + 1;
            } else { // 恰巧相等，则直接返回
                return middle;
            }
        }
        return res;
    }

✔ [367]有效的完全平方数 44.8% Easy 0.0%

本题和上一题类似，感觉简单一点。

本题我这解决的方法跟上一题有一点区别在于，在比较middle和x/middle时，比较的是double值，感觉更好一点。

有效的完全平方数，也就是说恰巧等于的时候返回true。

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }
        int left = 1;
        int right = num;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (middle > (double) num / middle) {
                right = middle - 1;
            } else if (middle < (double) num / middle) {
                left = middle + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}