复习：数据结构-数组题

二分查找

力扣题目 704. 二分查找

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

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

思路

题目前提是数组为有序数组，题目还强调数组中无重复元素。因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

二分法第一种写法

target 是在左闭右闭的区间里查找，即[left,right]。

1. 循环条件：
   • 使用 while (left <= right) 。这是因为当 left 和 right 相等时，它们指向的数组元素可能是要查找的目标元素。
2. 中间索引计算：
   • 使用 left + ((right - left) / 2) 来计算 middle，这样可以避免整数溢出。
3. 元素比较与指针更新：
   • 如果 nums[middle] == target，则找到目标元素，直接返回 middle。
   • 如果 nums[middle] < target，则更新 left = middle + 1，继续在右侧搜索。
   • 如果 nums[middle] > target，则更新 right = middle - 1，继续在左侧搜索。
4. 返回结果：
   • 如果循环结束后仍未找到目标元素，返回 -1 。
5. 特殊情况处理：
   • 如果数组为空，可以在开始时检查，并直接返回-1。
     代码如下：

class Solution {

    public int search(int[] nums, int target) {

        if (nums.length == 0){
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;

        while(left <= right){

            int mid = left + (right - left) / 2;
            
            if (nums[mid] > target){
                right = mid - 1;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

二分法第二种写法

target 是在左闭右开的区间里查找，即[left,right)。

1. 循环条件:
   • 使用 while (left < right) 。因为区间是左闭右开的，所以当 left 等于 right 时，实际上已经没有元素可以查找了，循环应该终止。
2. 中间索引计算:
   • 中间索引的计算方式与左闭右闭区间相同，使用 left + (right - left) / 2; 来防止整数溢出。
3. 元素比较与指针更新:
   • 如果 nums[middle] == target，则找到目标元素，直接返回 middle。
   • 如果 nums[middle] < target，则更新 left = middle + 1，继续在右侧搜索。
   • 如果 nums[middle] > target，则更新 right = middle。
   • 注意：这里是 right = middle 而不是 right = middle - 1，因为区间是左闭右开的。
4. 返回结果:
   • 如果循环结束后仍未找到目标元素，则返回 -1。
5. 特殊情况处理:
   • 与左闭右闭区间一样，开始处检查数组是否为空，并直接返回 -1。
     代码如下：

class Solution {

    public int search(int[] nums, int target) {

        if (nums.length == 0){
            return -1;
        }
      
        int left = 0;
        int right = nums.length - 1;

        while(left < right){

            int mid = left + (right - left) / 2;

            if (nums[mid] > target){
                right = mid;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

螺旋矩阵 II

力扣题目 59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例2：

输入：n = 1
输出：[[1]]

提示 ：1 <= n <= 20

思路

这一题很考验做题者对代码的掌控能力。我们使用左闭右开原则进行绘图。

如图所示，我们每次遍历一条边，都是以左闭右开来遍历，这样就不容易出错。
如果是奇数圈的话，我们就对其进行判断，手动将其填充即可。

代码如下：

class Solution {
    public int[][] generateMatrix(int n) {
        // 初始化一个要填充的目标矩阵
        int[][] matrix = new int[n][n];
        // 定义螺旋开始的行和列,标识我们在哪里开始填充矩阵
        int rowStart = 0;
        int columnStart = 0;
        // 定义螺旋的层级,标识我们正在填充的螺旋层级
        int level = 1;
        // 定义边界的偏移量,计算在每一层螺旋中，需要填充的行或列的范围
        int offset = 1;
        // 定义要填充的数字
        int number = 1;
        // 定义行和列的索引
        int row, column;

        // 当螺旋层级小于等于 n / 2 时，进行螺旋填充
        while(level <= n / 2){
            // 从左到右填充上方的行
            for(column = columnStart; column < n - offset; column++){
                matrix[rowStart][column] = number++;
            }
            // 从上到下填充右方的列
            for(row = rowStart; row < n - offset; row++){
                matrix[row][column] = number++;
            }
            // 从右到左填充下方的行
            for(; column > columnStart; column--){
                matrix[row][column] = number++;
            }
            // 从下到上填充左方的列
            for(; row > rowStart; row--){
                matrix[row][column] = number++;
            }
            // 更新螺旋开始的行和列，螺旋层级和边界偏移量
            rowStart++;
            columnStart++;
            level++;
            offset++;
        }
        // 如果 n 是奇数，填充中心的元素
        if(n % 2 != 0){
            matrix[rowStart][columnStart] = number;
        }
        return matrix;
    }
}

为什么循环是 n/2 次：

主要是理解螺旋填充的过程。在一个n x n的矩阵中，螺旋填充的过程可以看作是一层一层向内进行的。每一层都是一个环形，从外层开始，逐渐向内层进行。

因为对于一个n x n的矩阵，最多有n / 2层环形（如果n是奇数，中心的单个元素也被视为一层）。

例如，当n = 3时，矩阵如下：

1 2 3
8 9 4
7 6 5

这个矩阵有两层环形，外层环形包含元素1, 2, 3, 4, 5, 6, 7, 8，内层环形（一个点）包含元素9。
所以，当螺旋层级小于等于n / 2时，我们就继续进行螺旋填充，直到所有的环形层级都被填充完毕。