北京织梦网站建设,个人可以网站备案吗,创意平面设计公司,百度推广方案怎么写文章目录 Leetcode704 二分查找二分法的使用前提:区间选择其他注意事项 Leetcode27 移除元素解题思路:优化思路 Leetcode704 二分查找 链接#xff1a;https://leetcode.cn/problems/binary-search/ 代码随想录: https://programmercarl.com/ 时间复杂度: O(logN) 空间复杂度:… 文章目录 Leetcode704 二分查找二分法的使用前提:区间选择其他注意事项 Leetcode27 移除元素解题思路:优化思路 Leetcode704 二分查找 链接https://leetcode.cn/problems/binary-search/ 代码随想录: https://programmercarl.com/ 时间复杂度: O(logN) 空间复杂度: O(1) 二分法的使用前提:
没有重复元素数据结构是有序排列
区间选择
[left, right]: 此时left right的条件是有意义的, 在更新左右索引时均取mid_index的下一位[left, right): 此时循环条件为left right. 若 right则超过判断边界, 在更新右索引时取mid的值
其他注意事项
避免数据溢出: mid_index left ((right - left) 1), 等同于(right left) / 2, 但更安全高效除以2可以使用移位操作 1
int search(vectorint nums, int target) {if (nums.empty()) {return -1;}int left 0, right nums.size() - 1;while (left right) {int mid_index left ((right - left) 1);int mid_value nums[mid_index];if (mid_value target) {return mid_index;} else if (mid_value target) {left mid_index 1;} else {right mid_index - 1;}}return -1;
}Leetcode27 移除元素 链接:https://leetcode.cn/problems/remove-element/ 时间复杂度: O(N) 空间复杂度: O(1) 解题思路:
双指针法 即一个指针遍历数组, 一个指针指向需要更新的位置 该方法的问题是: 在最坏情况下, 如若开头第一个元素相等, 后续均不等, 则左指针指向的位置也需要更新n-1次. 该种情况下, 需要遍历该序列至多两次.
优化思路
int removeElement(vectorint nums, int val) {int val_index 0; // 数值索引for (int i 0; i nums.size(); i) {if (nums[i] ! val) {if (i ! val_index) { // 减少数据访问和赋值操作nums[val_index] nums[i];}val_index;}}return val_index;
}
