数组理论基础，704. 二分查找，27. 移除元素
二分查找
有序无重复元素数组中查找某个元素。 难点：
- 注意left，right更新时是middle还是middle+/-1，对于左闭的，不需要+/-1，因为/2向下取整对应就是区间靠左的元素，是一致的。
- 循环的终止条件是left<=right还是left==right。
- right = middle - 1，这是反直觉的，应为边界在向左收缩时要更新右边界值。
前两个边界条件都直接跟搜索区间的定义有关，搜索区间是一个不变量，在查找过程中定义不能出现歧义,O(logn)，因为可以抽象为二叉树节点，节点数量是N = 2^n（n是树的高度），每次搜索只走一个分支复杂度就是Log2(N)。
左闭右闭写法
- left = right是合法区间，所以left <= right，初始搜索区间是[0,nums.size() - 1]。
- 更新区间边界索引不能包含middle（上次搜索已经确定nums[middle] != target,更新时边界再包含middle，由于左闭右闭，就把不是搜索区间的值放入，出现问题）,left = middle + 1,right = middle - 1。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right) {
int middle = left + (right - left) / 2;
if(nums[middle] > target) {
right = middle - 1;
} else if(nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
};
middle = left + (right - left) / 2可以防止越界, 等同于 middle = （left + right)/2,对于左闭右闭middle =（left + right + 1）/2 也可以。
左闭右开写法
- left = right不合法，left < right,初始搜索区间[0,nums.size())。
- 更新区间边界索引时，right = middle，因为右开正好表示不包含middle，left = middle + 1。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while(left < right) {
int middle = left + (right - left) / 2;
if(nums[middle] > target) {
right = middle;
} else if(nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
return -1;
}
};
左开右闭
不常见，left < right，初始区间(-1,nums.size() -1]。right = middle - 1, left = middle。这里注意mid值要+1向上取整，因为左开右闭，如果还向下取整，只有两个元素的时候left值一直等于mid没办法等于right死循环（mid向下取整等于left，left又等于middle，死循环），而左闭右开就不会有这问题。
- 根据边界收缩情况写对应的 mid 计算公式，看见 left = mid + 1 (左闭) 就写 mid 下取整：mid=(left+right)/2、看见 left = mid （左开）就写 mid 上取整:mid=(left+right+1)/2;
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = -1;
int right = nums.size() - 1;
while(left < right) {
int middle = left + (right - left + 1) / 2;
if(nums[middle] > target) {
right = middle - 1;
} else if(nums[middle] < target) {
left = middle;
} else {
return middle;
}
}
return -1;
}
};
左开右开
不推荐，容易死循环，left < right - 1 (注意(1,2)区间是没意义的)，初始区间(-1,nums.size())。right = middle, left = middle。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = -1;
int right = nums.size();
while(left < right - 1) {
int middle = left + (right - left) / 2;
if(nums[middle] > target) {
right = middle;
} else if(nums[middle] < target) {
left = middle;
} else {
return middle;
}
}
return -1;
}
};
移除元素
暴力
第一次循环找要移除的元素，第二次循环移动后面的元素，注意下标和size更新-1，O(n^2)。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for(int i = 0; i < size; i++) {
if(nums[i] == val) {
for(int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--;
size--;
}
}
return size;
}
};
双指针（快慢指针）
快指针先扫一遍，遇到不需要删除的值就更新慢指针的索引和数组的值，这样一遍for循环就能完成删除。总结来说，快指针寻找新数组需要的元素，满指针指向新数组的索引，O(n)。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
int slowIndex = 0;
int fastIndex = 0;
for(fastIndex; fastIndex < size; fastIndex++) {
if(nums[fastIndex] != val) {
nums[slowIndex ++] = nums[fastIndex];
}
}
return slowIndex;
}
};
C#代码
二分查找：
public class Solution {
public int Search(int[] nums, int target) {
int left = -1;
int right = nums.Length - 1;
while(left < right) {
int mid = left + (right - left + 1) / 2;
if(nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] < target) {
left = mid;
} else {
return mid;
}
}
return -1;
}
}
移除元素：
public class Solution {
public int RemoveElement(int[] nums, int val) {
int slowIndex = 0;
int fastIndex = 0;
for(fastIndex = 0; fastIndex < nums.Length; fastIndex++) {
if(nums[fastIndex] != val) {
nums[slowIndex ++] = nums[fastIndex];
}
}
return slowIndex;
}
}
和C+的区别在于传参不需要&取数组地址，数组长度是xx.Length而不是vector.size()。
二三刷
704 二分查找
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
//左闭右闭
int search1(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) return mid;
if (target > nums[mid]) {
left = mid + 1;
}
if (target < nums[mid]) {
right = mid - 1;
}
}
return -1;
}
int search2(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) return mid;
if (target > nums[mid]) {
left = mid + 1;
}
if (target < nums[mid]) {
right = mid;
}
}
return -1;
}
};
int main() {
while (1) {
vector<int> test;
int n = -1;
int temp = -1;
int target = -1;
cin >> n;
Solution* s1 = new Solution;
for (int i = 1; i <= n; i++) {
cin >> temp;
test.push_back(temp);
}
cin >> target;
cout << s1->search2(test, target) << endl;
}
return 0;
}
27 移除元素
#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
int doit1(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) {
if (nums[i] == val) {
for (int j = i; j < size - 1; j++) {
nums[j] = nums[j + 1];
}
size--;
i--;
}
}
return size;
}
int doit2(vector<int>& nums, int val) {
int slow = 0;
int fast = 0;
while (fast < nums.size()) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
int main() {
while(1) {
int n = 0;
vector<int> s{};
int temp = 0;
int val;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> temp;
s.push_back(temp);
}
cin >> val;
Solution* s1 = new Solution();
int size = s1->doit2(s, val);
cout << size << endl;
for (int i = 0; i < size; i++) {
cout << s[i] << " ";
}
cout << endl;
delete s1;
}
return 0;
}
35.搜索插入位置（二分）
当没搜到时，left的位置恰好就是要插入的位置，当target>第一个元素时，left最终迭代结束后会再加1，就是要插入的位置，当target<第一个元素时，right会收敛到-1，而left维持0不动，还是插入位置。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int resIndex = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
}
if (nums[mid] > target) {
right = mid - 1;
}
}
return left;
}
};
使用ACM控制输入输出时注意，while(cin>>x)后EOF标志会残留在缓冲区内，为了不影响下次输入，需要清空缓冲区。
int main() {
Solution s1;
vector<int> s;
int i;
while (cin >> i) {
s.push_back(i);
}
//清空缓冲区
cin.clear();
cin.ignore();
int target;
cin >> target;
cout << s1.searchInsert(s, target);
return 0;
}
34 在排序数组中查找元素的第一个和最后一个位置（二分）
两次二分分别记录第一个和最后一个位置，当找到元素更新记录并向右收敛（left = mid + 1）得到最后一个位置,第一个位置以此类推。
class Solution {
public:
vector<int> res{-1, -1};
vector<int> searchRange(vector<int>& nums, int target) {
int first = -1;
int last = -1;
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
first = mid;
right = mid - 1;
}
if (target < nums[mid]) {
right = mid - 1;
}
if (target > nums[mid]) {
left = mid + 1;
}
}
left = 0;
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
last = mid;
left = mid + 1;
}
if (target < nums[mid]) {
right = mid - 1;
}
if (target > nums[mid]) {
left = mid + 1;
}
}
res[0] = first;
res[1] = last;
return res;
}
};
int main() {
Solution s1;
vector<int> s;
int i;
while (cin >> i) {
s.push_back(i);
}
cin.clear();
cin.ignore();
int target;
cin >> target;
vector<int> ans = s1.searchRange(s, target);
for (int item : ans) {
cout << item << " ";
}
return 0;
}
26删除有序数组中的重复项（快慢指针）
注意题目是非严格递增也就是说虽然有序但有重复元素，根据和前一个元素是否相等判断一下重复即可，如果不是有序的用哈希表扫一遍记录重复次数也可以。
- 注意，这题的最好解思路应该是fast指针不断和slow指针比较，而不是fast自己一个劲跑slow只负责记录，对应两种写法，当重复元素多的时候fast一个劲跑就很难解。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 0;
int fast = 0;
for (fast; fast < nums.size(); fast++) {
//fast一个劲跑，检测重复的
if (fast == 0 || fast > 0 && nums[fast] != nums[fast - 1]) {
nums[slow++] = nums[fast];
}
// fast遍历不断和slow比，注意slow-1才是上一个应该被保留的元素所移动到的指定位置
//if (slow == 0 || nums[fast] != nums[slow - 1]) {
//nums[slow++] = nums[fast];
//}
}
return slow;
}
};
80删除有序数组中的重复项II（快慢指针）
相比26，如果继续只考虑fast判断重复会有很多种情况，因为fast可能和slow更新后记录的元素冲突，不如原来fast前面没有2，slow更新完有2就会干扰重复判断，因此最优解是直接判断fast和slow-2的元素是否重复，因为是有序数组不可能存在1 2 1的情况，元素肯定是连续的。自己做的时候花了10min把所有条件都想出来了，实际上两种方式条件约化后是一样的。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
unordered_map<int, int> data;
if (nums.size() <= 2) return nums.size();
int slow = 2;
int fast = 2;
for (fast; fast < nums.size(); fast++) {
//if (nums[fast] != nums[fast - 1] || nums[fast] != nums[fast - 2] || nums[fast] == nums[fast - 2] && slow == fast - 1 && nums[slow - 1] != nums[slow - 2]) {
// nums[slow++] = nums[fast];
//}
if (nums[fast] != nums[slow - 2]) {
nums[slow++] = nums[fast];
}
}
return slow;
}
};
京公网安备 11010502036488号