代码随想录第一天|704.二分查找、27. 移除元素、977.有序数组的平方

1、二分查找

解题思路

1、前提条件：数组是升序排列的，这是二分查找的基础。

2、核心思想：每次都与当前区间的中间元素比较，将查找范围缩小一半。

3、终止条件：当左边界超过右边界时，说明目标值不存在，返回 -1。

方法一：左闭又闭

class Solution
{
public:
int search(vector<int> &nums, int target)
{
int lift = 0;
int right = nums.size() – 1;
while (lift <= right)
{
int middle = (lift + right) / 2;
if (target < nums[middle])
{
right = middle – 1;
}
else if (target > nums[middle])
{
lift = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
};

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle – 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle – 1

方法二：左闭又开

class Solution
{
public:
int search(vector<int> &nums, int target)
{
int lift = 0;
int right = nums.size();
while (lift < right)
{
int middle = (lift + right) / 2;
if (target < nums[middle])
{
right = middle;
}
else if (target > nums[middle])
{
lift = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
};

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

2、移除元素

解题思路

双指针法：

• 使用一个慢指针 k 来记录新数组的有效长度，同时也是下一个有效元素要放置的位置。
• 使用一个快指针 i 来遍历整个原数组。
• 当快指针指向的元素不等于目标值 val 时，就将其复制到慢指针的位置，然后慢指针向前移动一位。

  class Solution{
  public :
  int removeElement(vector<int> & nums, int val){
  int slow = 0;
  for (int fast = 0; fast < nums.size(); fast++)
  {
  if (nums[fast] != val)
  {
  nums[slow] = nums[fast];
  slow++;
  }
  }
  return slow;
  }
  }
  ;

• 时间复杂度：O(n)
• 空间复杂度：O(1)

3、有序数组的平方

解题思路

利用原数组非递减的特性，采用双指针法来高效生成平方后也非递减的新数组，时间复杂度可以优化到 O (n)。

1、数组元素平方后的最大值，只可能出现在原数组的最左端或最右端。

2、用指针 left 指向数组开头，right 指向数组末尾。

3、比较 nums[left] 和 nums[right] 的绝对值，将较大值的平方从结果数组的末尾开始向前填充。

class Solution
{
public:
vector<int> sortedSquares(vector<int> &nums)
{
int k = nums.size() – 1;
vector<int> result(nums.size(), 0);
for (int lift = 0, right = nums.size() – 1; lift <= right;)
{
if (nums[lift] * nums[lift] < nums[right] * nums[right])
{
result[k] = nums[right] * nums[right];
k–;
right–;
}
else
{
result[k] = nums[lift] * nums[lift];
k–;
lift++;
}
}
return result;
}
};

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。