算法训练营第1天｜704.二分查找、27.移除元素、977.有序数组的平方

/**
 * 左闭右开
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
    let left = 0, right = nums.length;
    // 当left=right时，由于nums[right]不在查找范围，所以没必要包括此情况。
    // 但是这种情况稳妥，可以不考虑边界
    while (left < right) {
      // 位运算 + 防止大数溢出
      // 定义两个接近最大安全整数的数
      // const left = Number.MAX_SAFE_INTEGER;
      // const right = Number.MAX_SAFE_INTEGER;

      // 直接相加会导致溢出
      // const badMiddle = Math.floor((left + right) / 2);
      // console.log('直接相加得到的中间值:', badMiddle); // 输出一个错误的结果

      // 使用安全的方法计算中间值
      // const goodMiddle = Math.floor(left + (right - left) / 2);
      // console.log('安全方法得到的中间值:', goodMiddle); // 输出


      // const mid = left + ((right - left) >> 1); 简单位移动
      const mid = left + ((right - left) / 2);
      // 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；
      // 由于right本来就不在查找范围内，所以将右边界更新为中间值，如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围
      if (nums[mid] > target) {
        right = mid;  // 去左区间寻找
      } else if (nums[mid] < target) {
        left = mid + 1;  // 去右区间寻找
      } else {
        return mid;
      }
    }
    return -1;
};

/**
 * 左闭右闭
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let left = 0, right = nums.length - 1
    // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
    while(left <= right) {
      // 位运算 + 防止大数溢出 取中间值
      const mid = left + ((right - left) >> 1);
      if(nums[mid] === target) {
        return mid
      // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；
      // 如果右边界更新为mid，那中间数还在下次查找范围内
      } else if(nums[mid] < target) {
        // 去右面闭区间寻找
        left = mid + 1
      } else {
        // 去左面闭区间寻找
        right = mid - 1
      }
    }
    return -1
};

/**
 * 暴力解法
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
  let size = nums.length
  for (let i = 0; i < size; i++) {
    if (nums[i] === val) {
      // 将后面的元素整体前移
      for (let j = i; j < size; j++) {
        // 赋值操作，将后面的元素赋给前一个元素
        nums[j] = nums[j + 1]
      }
      // 每一次成功前移，都会造成外层下标需要前移，才能保证下一个元素能被正确检测
      // 当移除一个等于 val 的元素后，数组中该位置会被后面的元素覆盖。如果不进行 i-- 操作，外层循环的索引 i 会继续向后移动，这样就会跳过刚刚移动到当前位置的新元素。因此，执行 i-- 可以让外层循环再次检查当前位置的新元素，确保不会遗漏任何等于 val 的元素。
      // 假设数组 nums = [3, 2, 2, 3]，val = 3。当 i = 0 时，nums[0] 等于 val，因此会将后面的元素向前移动一位，数组变为 [2, 2, 3, _]。如果不执行 i--，i 会变为 1，这样就会跳过新移动到 nums[0] 的元素 2。执行 i-- 后，i 仍然为 0，下一次循环会再次检查 nums[0]，确保不会遗漏任何等于 val 的元素。
      i = i - 1
      // 每一次成功前移，都会造成数组的长度减1
      size = size - 1
    }
  }
  return size
};

/**
 * 双指针法（快慢指针）
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
  // 慢指针
  let slowIndex = 0
  // 快指针
  for (let falseIndex = 0; falseIndex < nums.length; falseIndex++) {
    // 如果慢指针所对应的值不为目标值
    if (nums[slowIndex] !== val) {
      // 并且把快指针的值赋值给慢指针
      // 如果相等过，则当下一次不相等时，慢指针指向的元素就会被覆盖为不相等的元素，
      // 也就相当于和目标值相等的元素被原地删除了
      nums[slowIndex] = nums[falseIndex]
      // 慢指针+1
      slowIndex = slowIndex + 1
    }
  }
};

/**
 * 暴力解法
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
  // 直观明了的暴力解法
  return nums.map(item => {
    return item * item
  }).sort((a, b) => a-b)
};

/**
 * 双指针解法
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
  // i指向起始位置，j指向终止位置
  let i = 0, j = nums.length - 1, k = nums.length - 1
  // 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
  const res = new Array(nums.length).fill(0)
  while (i <= j) {
    // 得出平方值
    let left = nums[i] * nums[i]
    let right = nums[j] * nums[j]
    if (left < right) {
      // 右边的大，就把右边的平方值放到新数组
      // 新数组上的指针向左移动
      res[k--] = right
      // 并且右边的指针向左移动
      j--
    } else {
      // 左边的大，就把左边的平方值放到新数组
      // 新数组上的指针向左移动
      res[k--] = left
      // 并且左边的指针向右移动
      i++
    }
  }
  return res
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    // 双指针
    let res = []
    // 定义左右指针
    let left = 0, right = nums.length - 1

    while(left <= right) {
        const le = nums[left] * nums[left]
        const ri = nums[right] * nums[right]
        if(le < ri) {
            // 给数组前增加元素
            res.unshift(ri)
            // 右边的大，右边指针向左移动
            right --
        } else {
            // 左边的大，左边指针向右移动
            res.unshift(le)
            left ++
        }
    }

    return res

};