题目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
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
思路
这道题主要考察的是二分法，在使用二分法时要考虑好每次分割的左右边界，主要的分割方式有两种：1.左右边界全闭合([left, right]) 2.左闭右开([left, right).
代码
1.左右边界全闭合[left, right]
class Solution {
public:
int search(vector<int>& nums, int target) {
int index = (nums.size() - 1) / 2;
int lft = 0, rht = nums.size() - 1;
while(lft <= rht)
{
if(nums[index] == target)
{
return index;
}
else if(nums[index] < target)
{
lft = index + 1;
index = (lft + rht) / 2;
}
else
{
rht = index - 1;
index = (lft + rht) / 2;
}
}
return -1;
}
};
2.左闭右开[left, right)
//[lft, rht)
class Solution {
public:
int search(vector<int>& nums, int target) {
int index = (nums.size() - 1) / 2;
int lft = 0, rht = nums.size();
while(lft < rht)
{
if(nums[index] == target)
{
return index;
}
else if(nums[index] < target)
{
lft = index + 1;
index = (lft + rht) / 2;
}
else
{
rht = index;
index = (lft + rht) / 2;
}
}
return -1;
}
};
题目2 27. 移除元素
题目描述：
给定一个 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
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
思路
这道题使用双指针法可以用一轮遍历完成指定元素的筛选与去除，双指针slow与fast分别进行非指定元素的复制与指定元素的筛选。
代码
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];
}
}
return slow;
}
};
题目3 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 已按 非递减顺序 排序
思路
这道题可以先平方然后直接调用sort来进行排序，但这种方法的时间复杂度是O(n+nlgn)=O(nlgn)。另一种方法是使用双指针的方法来排序，利用双指针遍历原始的数组加上赋值给新数组的遍历，时间复杂度为O(2*n)=O(n)。
代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> results(nums.size());
int lft = 0, rht = nums.size() - 1;
int cur = results.size() - 1;
while(lft < rht)
{
int l = nums[lft] * nums[lft];
int r = nums[rht] * nums[rht];
if(l <= r)
{
rht--;
results[cur--] = r;
}
else if(l > r)
{
lft++;
results[cur--] = l;
}
}
results[cur] = nums[lft] * nums[lft];
return std::move(results);
}
};