Day 1 二分查找&双指针

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]之间。

思路

二分查找，采用左闭右闭更符合我的思维习惯。

代码

class Solution {
  public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {  // 由于是左闭右闭，因此left == right是有意义的
      int mid = (left + right) / 2;
      if (nums[mid] > target) {
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }
}

27. 移除元素

题目描述

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

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

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

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 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

思路

本题可以使用暴力法求解，且不会超时。

// 暴力法
class Solution {
  public int removeElement(int[] nums, int val) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
      if (nums[i] == val) {
        for (int j = i; j < len - 1; j++) {
          nums[j] = nums[j + 1];
        }
        i--;  // 所有元素向前移动了一位，因此为移动到下一个元素i实际上不需要再向前
        len--;
      }
    }
    return len;
  }
}

更快速的方法是使用双指针法（具体而言是快慢指针）。快慢指针的思路是：维护一快一慢两个指针，初始化时都指向位置0.每进行一次循环，无论如何快指针都会前进一位，而慢指针的前进则有条件：当快指针指向位置上的值不等于val时，慢指针才前进一位，此外将慢指针指向位置的值更新为快指针指向位置上的值。

快慢指针法中，慢指针实际上指向的是需要更新的位置，并且只有在快指针探索到合法值时才会前进，因此慢指针同时也记录了移除全部非法值之后的数组长度，也就是题目要求的返回值。

// 快慢指针法
class Solution {
  public int removeElement(int[] nums, int val) {
    int fastPointer = 0;
    int slowPointer = 0;
    while (fastPointer < nums.length) {
      if (nums[fastPointer] != val) {
        nums[slowPointer++] = nums[fastPointer];
      }
      fastPointer++;
    }
    return slowPointer;
  }
}

977. 有序数组的平方

题目描述

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

思路

本题可以使用暴力法求解，且不会超时。

// 暴力法
class Solution {
  public int[] sortedSquares(int[] nums) {
    int[] square = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
      square[i] = nums[i] * nums[i];
    }
    Arrays.sort(square);
    return square;
  }
}

也可以使用更快的双指针法。关键是注意到平方数的特点，即离数轴原点越远，平方数越大。由于nums已经按照非递减顺序排好，则可知该数组两端的数所得的平方数可能是最大的。因此维护两个指针，分别从头尾出发。

// 双指针法
class Solution {
  public int[] sortedSquares(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int[] result = new int[nums.length];
    int i = nums.length - 1;
    while (i >= 0) {
      if (nums[left] * nums[left] < nums[right] * nums[right]) {
        result[i] = nums[right] * nums[right];
        right--;
      } else {
        result[i] = nums[left] * nums[left];
        left++;
      }
    }
    return result;
  }
}