算法训练营day01 | {704.二分查找, 27.移除元素, 977.有序数组的平方}

第一章数组-part01，知识点为二分查找、双向指针。

0. 每日精华

算法训练营每日精华：有关于for循环、数组越界、递归如何debug的技巧总结，不过还没用上，每一日的题目在这有额外的精炼总结，感觉容易遗忘这个资源，记录一下提醒自己。

704. 二分查找

题目链接：704. 二分查找
文档讲解：代码随想录–704二分查找
视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找
状态：左闭右闭区间做法

1.1 看到题目的想法

有序数组的二分查找，之前已经做过很多次了，结合示例思路清晰，代码如下：

▶

AC解法

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, answer = -1;
        int high = nums.length - 1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                answer = mid;
                break;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            }
        }
        return answer; 
    }
}

1.2 看完代码随想录的想法

忽略了一些题目的前提条件，满足二分法的前提条件有：
- 数组有序
- 数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不唯一！
区间的定义有两种，我习惯的是第一种左闭右闭即[left, right]，第二种左闭右开[left, right)没想到。

其次，对比参考写法，我定义了一个冗余变量answer；在计算下标mid时应该考虑溢出问题，因此优化代码如下：

▶

第一种改进写法

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while(low <= high) {
            // 防止溢出 int mid = (low + high) / 2;
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            }
        }
        return -1; 
    }
}

熟悉第二种左闭右开的区间定义，考虑边界处理时，关注区间定义作为不变量，练习代码如下：

▶

AC解法2

class Solution {
    // 左闭右开
    public static int search2(int[] nums, int target) {
        int low = 0;
        int high = nums.length;
        while (low < high) { // 没有等号，因为在左闭右开下==没有意义
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else { // nums[mid] > target 应该去左边区间寻找，且区间保持左闭右开
                high = mid;
            }
        }
        return -1;
    }
}

27. 移除元素

题目链接：27. 移除元素
文档讲解：代码随想录–27移除元素
视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素
状态：花了较长的时间解题，一开始就是前后两指针移动，但边界处理想不清楚，Debug时间长。

2.1 看到题目的想法

题目要求给你一个数组nums，原地移除所有数值等于val的元素, 然后返回nums中与val不同的元素的数量。还是很好理解的，我和之前快排定位枢轴元素一样，定义了两个指针向中间移动，代码如下：

▶

自己的解法

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, answer = 0;
        int right = nums.length - 1;
        while (left < right) {
            while(left < right && nums[left] != val) {
                left++;
            }
            // 找到第一个不等于val的元素
            while(nums[left] == val && right >= 0 && nums[right] == val) {
                right--;
            }
            if (left < right) {
                // 交换元素
                nums[left] = nums[right];
                nums[right] = val;
            }
        }
        System.out.println(Arrays.toString(nums));

        // 再遍历一遍找下标
        for(int j = nums.length - 1; j >=0; --j) {
            if (nums[j] != val) {
                answer = j + 1;
                break;
            }
        }
        return answer;
    }
}

2.2 看完代码随想录的想法

双指针法（快慢指针法）和我想得不太一样啊，这种数组前移覆盖的方式，写起来很简短清晰。附上定义：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

按照动画，完善代码如下：

▶

快慢指针法

// 快慢指针法
public static int removeElementV2(int[] nums, int val) {
    int slowIndex = 0;
    for(int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
        if (val != nums[fastIndex]) {
            nums[slowIndex++] = nums[fastIndex];
        }
    }
    return slowIndex;
}

我的做法属于相向双指针法，写得不太优雅，有冗余的检索下标操作，需要优化，完善如下：

▶

相向双指针法

// 相向双指针法
public static int removeElementV3(int[] nums, int val) {
    int left = 0;
    int right = nums.length - 1;
    // 将right移动到从右数第一个值不为val的位置
    while(right >= 0 && nums[right] == val) right--;
    while (left <= right) {
        // left位置的元素需要被覆盖，用right元素覆盖
        if (nums[left] == val) {
            nums[left] = nums[right];
            right--;
        }
        left++;
    }
    return left;
}

977.有序数组的平方

题目链接：977.有序数组的平方
文档讲解：代码随想录–977有序数组的平方
视频讲解：双指针法经典题目 | LeetCode：977.有序数组的平方
状态：暴力解题，直接平方之后再快速排序，快排参考了之前考研的刷题记录，还没领悟双指针思想。

3.1 看到题目的想法

题目要求给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。本来想开三个数组，降低时间复杂度，但考虑到负数平方之后的数组仍然是一个无序的子数组，还是需要用到快排，所以没想到好的解题方法，时间复杂度nlogn。

▶

自己的解法

class SortedSquares {
    /**
     * 输入：nums = [-4,-1,0,3,10]
     * 输出：[0,1,9,16,100]
     * 解释：平方后，数组变为 [16,1,0,9,100]
     * 排序后，数组变为 [0,1,9,16,100]
     * 先全部平方然后快排排序一下  复杂度nlogn
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[i] * nums[i];
        }

        // 快排
        quickSort(0, ans.length - 1, ans);

        System.out.println(Arrays.toString(ans));

        return ans;
    }

    void quickSort(int left, int right, int[] nums) {
        if(left < right) {
            int position = partition(left, right, nums);
            quickSort(left, position - 1, nums);
            quickSort(position + 1, right, nums);
        }
    }

    // 确定序列的枢轴元素，并遍历使枢轴左边的元素都比它小，右边都比它大
    int partition(int left, int right, int[] nums) {
        int pos = (int)(Math.random() * (right - left + 1)) + left;
        swap(nums, left, pos);  // 交换保证快排性能

        int pivot = nums[left]; // 枢轴

        while(left < right) {
            while(left < right && nums[left] <= nums[right]) {
                right--;
            }
            swap(nums, left, right);
            while (left < right && nums[left] <= nums[right]) {
                left++;
            }
            swap(nums, left, right);
        }
        return left; // 枢轴
    }

    /**
     * 接收数组+两个索引，通过索引交换数组元素
     * @param arr
     * @param i
     * @param j
     */
    void swap(int[] arr, int i , int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

3.2 看完代码随想录的想法

哇，确实数组其实的有序的，只不过负数平方之后可能成为最大数了，那么数组平方的最大值一定就在数组的两端，不是最左边，就是最右边，不可能是中间。此时可以考虑使用双指针法，看到这里我明白了！非常清晰的解题思路，代码也不难写。

重新敲一遍代码，如下：

▶

双指针法

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] results = new int[nums.length];
        int i = 0, j = nums.length - 1, k = results.length - 1;
        while(i <= j) {
            if (nums[i] * nums[i] <= nums[j] * nums[j]) {
                results[k--] = nums[j] * nums[j];
                j--;
            } else {
                results[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return results;
    }
}

4. 今日收获

一直都很少刷题，今天算是迈出舒适圈了，然后Java是今年学的，在swap交换数组元素那里，没有把数组索引传过去，导致内存中的数组元素没有被更新，这个要注意。
今天学到了快慢指针法、以及有序数组的平方用到的双指针思想。
学习时长：4小时（题不难，熟悉了一下流程，以及写以后博客的模板花了一点时间）

Leetcode > 数组

#Java #代码随想录

算法训练营day01 | {704.二分查找, 27.移除元素, 977.有序数组的平方}

http://paopaotangzu.xyz/cn/day01_leetcode/

作者

PROTON TANG

发布于

2025年12月17日

许可协议

算法训练营day03 | {203. 移除链表元素, 707.设计链表, 206.反转链表} 下一篇