1. 常数操作
- 与数据量无关，每次都是固定时间内完成的操作
- int a = arr[i];
- +-*/，位运算
2. 非常数操作
-
与数据量有关
-
int b = list.get(i);
-
链表，需要遍历
-
评价一个算法流程的好坏：先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”
- 相同为0，不同为1
- 无进位相加
- 偶数个1为0
- 奇数个1为1
1. 异或的性质
- 0^N=N
- N^N=0
- 满足交换律和结合律
- a^b = b^a
- a^b^c = a^(b^c)
- 同一批数异或，结果是一样的（与顺序无关）
2. 交换两个数的值
- 前提：a和b在内存里是两块独立的区域 (抖机灵，不推荐)
int a = 17, b = 23;
a = a^b;
b = a^b;
a = a^b;3. 在一个整型数组中，只有一种数出现了奇数次，其他数都出现了偶数次，如何找到这一种数
void printOddTimesNum1(vector<int> & arr){
int eor = 0;
for(auto& cur : arr)
eor ^= cur;
cout << eor << endl;
}4. 有两种数出现了奇数次，其他数都出现了偶数次，如何找到这两种数
void printOddTimesNum2(vector<int> & arr){
int eor = 0;
for(int cur : arr){
eor ^= cur;
}
// eor = a^b;
// eor != 0; --> eor 必然有一个位置上是1
int rightOne = eor & (~eor + 1); //提取出最右侧的1
int onlyOne = 0; // eor'
for(auto& cur : arr){
if(cur & rightOne == 0){
onlyOne ^= cur;
}
}
cout << onlyOne << ", " << (eor ^ onlyOne) << endl;
}从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到整个数组排序。
void selectSort(vector<int>& arr){
if( arr.size() < 2){
return;
}
for (int i = 0; i < arr.size() - 1; i++){ // i ~ N-1
int minIndex = i;
for (int j = i + 1; j < arr.size(); j++){
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}从左到右不断交换相邻逆序的元素，在一轮循环之后，可以让未排序的最大元素上浮到右侧。
void bubbleSort(vector<int> & arr){
if( arr.size() < 2){
return;
}
for(int i = arr.size() - 1; i > 0; i--){
for (int j = 0; j < i; j++){
if(arr[j] > arr[j+1]){
swap(arr, j, j+1);
}
}
}
}- 与数据状况有关，最好情况下为O(N)
- 时间复杂度按照最差情况: O(N^2)
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
void insertionSort(vector<int> & arr){
if (arr.size() < 2){
return;
}
for(int i = 1; i < arr.size(); i++){ //0~i做到有序
for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--){ // 0~i-1 已经有序, j 当前位置的前一个位置
swap(arr, j, j+1);
}
}
}- 时间复杂度: O(logN)
- 每次砍一半，需要多少次可以把数组砍没
1. 一个有序数组，寻找某个数num是否存在
✅tested
int binarySearch(vector<int>& nums, int target) {
int low = 0;
int high = nums.size() - 1;
while(low <= high){
//int mid = (low + high) / 2;
int mid = low + ((high - low) >> 1);
if(nums[mid] == target){
return mid; // find
}
else if(nums[mid] > target){
high = mid - 1;
}
else{
low = mid + 1;
}
}
return -1; //not found
}2. 在一个有序数组中，找>=某个数num最左侧的位置
✅tested
int binarySearch_01(vector<int>& nums, int target){
int low = 0;
int high = nums.size() - 1;
int index = -1;
while (low <= high){
//int mid = (low + high) / 2;
int mid = low + ((high - low) >> 1);
if(nums[mid] >= target){
index = mid;
high = mid - 1;
}
else if(nums[mid] < target){
low = mid + 1;
}
}
return index;
}3. 数组无序，任何两个相邻数一定不相等，求局部最小值
注：代码为局部最大值，最小值同理
✅tested
int findPeakElement(vector<int>& nums) {
int n = nums.size();
if(n == 1){
return 0;
}
//先判断两边情况
if(nums[0] > nums[1]){
return 0;
}
else if(nums[n - 1] > nums[n - 2]){
return n - 1;
}
int low = 0;
int high = n - 1;
while(low <= high){
int mid = low + ((high - low) >> 1);
// 当前为峰值
if(mid >= 1 && mid < n - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]){
return mid;
}
else if(mid >= 1 && nums[mid] < nums[mid - 1]){
// 峰值在 mid 左侧
high = mid - 1;
}
else if(mid < n - 1 && nums[mid] < nums[mid + 1]){
// 峰值在 mid 右侧
low = mid + 1;
}
}
return -1;
}- 有一个你想要测得方法a
- 实现复杂度不好但是容易实现的方法b
- 实现一个随机样本产生器
- 把方法a和方法b跑相同得随机样本，看看得到的结果是否一样
- 如果有一个随机样本使得对比结果不一致，打印样本进行人工干预，改对方法a或者方法b
- 当样本数量很多时，比对测试依然正确，可以确定方法a正确