有序数组的平方 && 移除数组 && 二分查找

Shark Xu 2023/1/3 LeetCode

# 有序数组的平方

这是力扣 977 题

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

# 解题思路

继上一道题使用到双指针、API、暴力解法，又刷到一道类似的题目，来巩固一下这三种解法。这题描述的很清楚，就是将一组数组里的数平方之后再通过排序输出，十分容易理解。因此，这里也可以使用到暴力配合 API 解法以及双指针解法。

# 暴力配合 API 解法

暴力解法就不用我多说了吧，使用一层 for 循环遍历，然后进行求平方。排序可以通过调用 API 即 sort 函数来解决。思路过程十分简单，看代码也是一看就会。

相关代码如下：

var sortedSquares = function(nums) {
    var arr = [];
    for(let i = 0;i<nums.length;i++){
        arr.push(nums[i]*nums[i]);
    }
    let Arr = arr.sort(function(a,b){return a-b});
    return Arr
};

这样一看暴力解法是不是很简单。但是还是存在那个问题，时间复杂度。因此，下面将来介绍双指针解法。

# 双指针解法

var sortedSquares = function(nums) {
   //双指针解法
   let n = nums.length;
    let res = new Array(n);
    let i = 0, j = n - 1, k = n - 1;
    while (i <= j) {
        let left = nums[i] * nums[i],
            right = nums[j] * nums[j];
        if (left < right) {
            res[k--] = right;
            j--;
        } else {
            res[k--] = left;
            i++;
        }
    }
    return res;
};

在此题中，i 指向起始位置，j 指向终止位置。然后定义一个新数组 res，和 nums 数组一样的大小，让 k 指向 res 数组终止位置。这里输出的原则就是：因为数组是有序的，正常情况下进行平方后也是正常排序。但是负数的平方可能会成为最大值，所以需要通过比较来判断最大值是在数组的最左边还是在最右边。

相比较于暴力配合 API 解法，双指针解法会难理解些，但是它的时间复杂度降低了很多。因此大家可以多去尝试一下，理解双指针解法。

# 移除数组

这是力扣 27 题

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

# 解题思路

此题中有一个很重要的条件，你必须仅使用 O(1) 额外空间并原地修改输入数组。空间复杂度 O(1)、原地移除，这都是已经规定好了的。这里将介绍双指针、API、暴力三种解法。

# 双指针解法

双指针又称为快慢指针，通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。快慢指针在解题中也是经常使用，掌握好它能解决很多相关问题的。

快慢指针的定义：

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

相关代码如下：

var removeElement = function(nums, val) {
    const n = nums.length;
    let left = 0;
    for (let right = 0; right < n; right++) {
        if (nums[right] !== val) {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;

# API 解法

使用 js 中的数组方法 splice()，对数组进行一层for循环即可。splice() 方法用于添加或删除数组中的元素。在循环过程中如遇到与目标值相等的元素，就可以使用 splice() 方法来删除数组的元素从而达到效果。

相关代码如下：

var removeElement = function(nums, val) {
    for(var i=0;i<nums.length;i++){
        if(nums[i]===val){
            nums.splice(i,1)
            i--
        }
    }
    return nums.length
};

# 暴力解法

暴力解法相信大家都了解或者都用过，遇事不决就暴力。暴力解法是最基本也是最简单的解题思路，但是它的缺点是时间复杂度太高了。在此题中，可以使用两层for循环，一层遍历数组元素，一层更新数组元素，所以时间复杂度为O(n*n)。（暴力解法比较普遍，所以这里就不附上代码了）

# 二分查找

这是力扣 704 题

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

不难看出，这是一道典型的二分查找的问题（毕竟题目名就叫二分查找）。对于二分查找，有着专门的解题思路和技巧。

# 解题思路

什么是二分法，简单点理解就是对数据进行对半查找。二分法会涉及到很多边界条件，二分法的难点就在于如何处理边界问题。例如到底是 while(left < right) 还是 while(left <= right)。

在二分法中区间有左闭右闭和左闭右开两种定义。下面将用这左闭右闭区间的方法来讲解一下此题。

# 左闭右闭

左闭右闭就是[left,right]，所以在这里需要判断是while(left < right)还是while(left <= right)。

# 边界问题

对于边界问题，可以这么去想：如果是while(left < right)，说明left一定是只能小于right的，如果是while(left <= right)，说明left等于right是成立的。因为我们使用左闭右闭区间，所以left = right，所以可以使用while(left <= right)。同理，如果使用左闭右开区间，就是使用while(left < right)，因为左闭右开区别没有left = right。

# 中间值问题

除了while问题，这里还有一个middle问题。在左闭右闭的情况下，如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为middle-1；如果右边界更新为middle，那中间数还在下次查找范围内。在左闭右开的情况下，如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应该要在。因为左闭右开，所以right不在查找范围内，所以将右边界更新为中间值，如果更新右边界为mid-1，则将中间值的前一个值就会查找不到了。

相关代码如下：

var search = function(nums, target) {
    let left = 0;
    let right = nums.length-1;
    while(left<=right){
        let middle = Math.floor((right+left)/2);
        if(nums[middle]>target){
            right = middle-1;
        }else if(nums[middle]<target){
            left = middle+1;
        }else{
            return middle
        }
    }
    return -1;
};

了解了while和middle问题，现在来看代码是不是很容易理解了。这样一来，这个简单的二分查找就解决了。

翻转链表 && 移除链表元素 && 长度最小的子数组有序数组的平方 && 移除数组 && 二分查找

Shark Xu 的博客

Choose mode