題目1: 704. 二分查找
算法思路:
采用雙指針法沦零,分別兩個指針指向數組的第一個和最后一個元素路操,循環(huán)取二者中間元素屯仗,如果中間元素就是所需元素直接返回,如果目標元素小于中間元素魁袜,則只需要在[left, mid - 1]間查找峰弹,否則需要在[mid+1, right]間查找芜果。如果最終找不到,返回-1.
代碼如下:
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) return mid;
if(target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
return -1;
}
};
題目2: 27. 移除元素
算法思路:依然是雙指針法蚁吝,定義一個指針k,用i循環(huán)遍歷數組所有元素窘茁,如果當前元素不等于目標元素脆烟,那么將當前元素存入nums[k].
代碼:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] != val) {
nums[k++] = nums[i];
}
}
return k;
}
};
題目3: 977. 有序數組的平方
算法思路:
將當前數組所有元素的平方依次存入到另一個數組中浩淘。
使用兩個指針分別指向新數組的首尾元素,二者的較大值即為所求數組的最大值张抄,然后再對剩余部分遍歷處理即可。
代碼:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> sorted = vector<int>(nums.size());
for(int i = 0; i < nums.size(); i++) {
sorted[i]= nums[i] * nums[i];
}
int i = nums.size() - 1;
int left = 0;
int right = sorted.size() - 1;
while(left <= right) {
if(sorted[left] > sorted[right]) {
nums[i--] = sorted[left++];
}
else {
nums[i--] = sorted[right--];
}
}
return nums;
}
};