下面代码就是实现一个二分查找法
int mid = (l+r)/2;这一行里面有一个这样的 bug，当 l 和 r 超级大之后，会产生整型溢出的情况
这个 bug 的修复，我们选择这样的改写方法：int mid = l + (r-l)/2;
#include <iostream>#include <cmath>#include <cassert>#include <ctime>
using namespace std;
template<typename T>int binarySearch(T arr[],int n,T target){// 左边界是0 有边界是n-1 int l = 0,r = n-1; while (l<r){// int mid = (l+r)/2; int mid = l + (r-l)/2; if (arr[mid] == target){ return mid; } if (target>arr[mid]) l = mid+1; else r = mid-1; } return -1;}
int main() { int arr1[7] = {1,2,5,7,9,12,16}; clock_t starttime = clock(); int index = binarySearch( arr1,7,12); clock_t endtime = clock(); cout<<index<<endl; cout<<double(endtime-starttime)/CLOCKS_PER_SEC<<endl; return 0;}
复制代码
eg：leetcode 算法 283
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
1 首先第一种解法中，就是创造一个新的空间，把不是 0 的数据提取出来，再存放进去，后面的全部置位 1.
void moveZeros(vector<int>& nums){ vector<int> nonZeroElements;
for (int i = 0; i < nums.size(); ++i) { if(nums[i] != 0){ nonZeroElements.push_back(nums[i]); } } //将非0数组送入 for (int i = 0; i < nonZeroElements.size(); ++i) { nums[i] = nonZeroElements[i]; } for (int i = nonZeroElements.size(); i < nums.size(); ++i) { nums[i] = 0; } }
复制代码
2 采用双指针的方法
这里需要多考虑一点，如果全都是非 0 元素，不加 k！=i 这个 if 判断条件，会导致效廉过慢。
void moveZeroes(vector<int>& nums) { int k = 0; for(int i = 0; i<nums.size();++i){ if (nums[i]){ if(k!=i){ nums[k++] = nums[i]; }else{ k++; } } } for (int j = k; j < nums.size(); ++j) { nums[j] = 0; } }
复制代码
下图就是添加 if 判断之后，对比算法时间差距
leetcode 中 26 27 还有 80 都是相似的题型
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
解 1：
class Solution {public: void sortColors(vector<int>& nums) { int count[3] = {0,}; for(int i =0;i<nums.size();i++){ count[nums[i]]++; } int index = 0; for(int i = 0; i<count[0];i++){ nums[index++] = 0; } for(int i = 0; i<count[1];i++){ nums[index++] = 1; } for(int i = 0; i<count[2];i++){ nums[index++] = 2; } }};
复制代码
解 2：使用 3 路快排的思想
评论