二分查找

力扣题目 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) 。这是因为当 leftright 相等时,它们指向的数组元素可能是要查找的目标元素。
  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 ,生成一个包含 1n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例1
2024-04-21T23:04:39-dqzqxlbh.jpg

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

示例2

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

提示 :1 <= n <= 20

思路

这一题很考验做题者对代码的掌控能力。我们使用左闭右开原则进行绘图。
2024-04-22T13:42:06-xpleyvad.png

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

代码如下:

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时,我们就继续进行螺旋填充,直到所有的环形层级都被填充完毕。

移除元素

力扣题目 27. 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:

  • 更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k

示例 1:

输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2,,]
解释: 你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。

示例 2:

输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5, nums = [0,1,4,0,3,,,]
解释: 你的函数应该返回 k = 5,并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

思路

这一道题呢,我使用的方法有两种:

  • 暴力法
  • 双指针法(快慢指针)

暴力解法(不推荐)

直接两层for循环,外层循环遍历数组元素,内层循环更新数组元素。如下图:

2024-06-04T20:17:18-hhamenrl.png

C++:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int currentSize = nums.size();  // 当前数组的大小
        for (int i = 0; i < currentSize; i++) {
            if (nums[i] == val) { // 如果当前元素是需要移除的元素
                // 内部循环:将数组中后续的所有元素向前移动一位
                for (int j = i + 1; j < currentSize; j++) {
                    nums[j - 1] = nums[j]; // 将位置j的元素移动到位置j-1
                }
                i--; // 因为当前位置i的元素已经被移除,需将i回退一位,以检查新的当前元素
                currentSize--; // 数组大小减一,因移除一个元素
            }
        }
        return currentSize; // 返回移除指定元素后的数组大小
    }
};
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)

双指针法

可以定义一个快指针和一个慢指针在一个for循环下完成两个for循环所做的事。

  1. 快指针:负责遍历整个数组。目的是找到新的数组的元素,即不包含目标元素 val 的所有元素。
  2. 慢指针:指向要更新的位置

如下图:
2024-06-04T20:17:18-liglbmvh.png

C++:

class Solution {
public:
    int removeElement(std::vector<int>& nums, int val) {
        int i = 0; // 慢指针
        for (int j = 0; j < nums.size(); j++) { // 快指针
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
};
// 时间复杂度:O(n)
// 空间复杂度:O(1)

努力有时候战胜不了天分,但至少能让别人看得起你