C++数据结构与算法（一）（复杂度、数组二分查找）

时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

假设算法的问题规模为n，算法的渐近时间复杂度，简称时间复杂度，记为 O ( f ( n ) ) O(f(n)) O(f(n))。

大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
但是业内的一个默认规定，O代表的就是一般情况，而不是严格的上界。
深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的。

O(1)常数阶 < O ( log ⁡ n ) O(log n) O(logn)对数阶 < O ( n ) O(n) O(n)线性阶 < O ( n log ⁡ n ) O(nlog n) O(nlogn) < O ( n 2 ) O(n^2) O(n2)平方阶 < O ( n 3 ) O(n^3) O(n3)立方阶 < O ( 2 n ) O(2^n) O(2n)指数阶 < O ( n ! ) O(n!) O(n!) < O ( n n ) O(n^n) O(nn)log n忽略底数的描述

空间复杂度

空间复杂度预估程序运行时占用内存的大小，而不是可执行文件的大小。

数组

数组是存放在连续内存空间上的相同类型数据的集合。

二分查找

在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较nums[ i ] 和 target 的大小：

如果 n u m s [ i ] = t a r g e t nums[i] = target nums[i]=target，则下标 i 即为要寻找的下标;如果 n u m s [ i ] > t a r g e t nums[i] > target nums[i]>target，则 target只可能在下标i的左侧;如果 n u m s [ i ] < t a r g e t nums[i] < target nums[i]target只可能在下标i的右侧。

基于上述事实，可以在有序数组中使用二分查找寻找目标值，每次查找都会将查找范围缩小一半。

时间复杂度： O ( log ⁡ n ) O(log n) O(logn)，其中 n 是数组的长度空间复杂度： O ( 1 ) O(1) O(1)

每次循环中 left 和 right 共同约束了本次查找的范围， 要让本次循环与上一次循环查找的范围既不重复(重复了会引起死循环)， 也不遗漏， 并且要让 left 和 right 共同约束的查找的范围变得无意义时不再进行查找（即跳出 while）(否则会导致访问越界)， 这其实就是所谓的循环不变量。因此要清楚对查找区间的定义，在循环中根据查找区间的定义来做边界处理。

定义查找区间为 [left, right] 或 [left, right)，LeetCode示例：

704、二分查找

class Solution {public: int search(vector& nums, int target) { // 1、定义查找区间为 [left, right] int left = 0; int right = nums.size() - 1; // [left, right] while (left <= right){ int middle = left + (right - left) / 2; //防溢出 if (nums[middle] > target){ right = middle - 1;// [left, right] } else if (nums[middle] < target){ left = middle + 1;// [left, right] } else{ return middle; } } return -1; // 2、定义查找区间为 [left, right) int left = 0; int right = nums.size();// [left, right) while (left < right){ int middle = left + (right - left) / 2; if (nums[middle] > target){ right = middle;// [left, right) } else if (nums[middle] < target){ left = middle + 1;// [left, right) } else{ return middle; } } return -1; // 查找失败 }};

35、搜索插入位置

class Solution {public: // 无重复元素 int searchInsert(vector& 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{ // nums[middle] == target return middle; // 无重复元素 } } return left; // = right + 1 }};

循环判断中，等于target的情况不跳出循环，继续移动搜索指针，最终将会导致 left = right + 1 的情况而跳出循环。

class Solution {public: int searchInsert(vector& 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 right = middle - 1;// 最后一个小于 num 的位置索引 } else{ // nums[middle] < target// 小于即 右移left left = middle + 1;// 第一个大于或等于 num 的位置索引 } } // 有重复元素 // 寻找第一个大于或等于 num 的位置索引，返回left return left; // = right + 1 // 寻找最后一个小于 num 的位置索引，返回right // return right; // = left + 1 }};

class Solution {public: int searchInsert(vector& 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 right = middle - 1;// 最后一个小于或等于 num 的位置索引 } else{ // nums[middle] <= target// 小于或等于 即 右移left left = middle + 1;// 第一个大于 num 的位置索引 } } // 有重复元素 // 寻找第一个大于 num 的位置索引，返回left return left; // = right + 1 // 寻找最后一个小于或等于 num 的位置索引，返回right // return right; // = left + 1 }};

34.在排序数组中查找元素的第一个和最后一个位置

1、遍历

class Solution {public: vector searchRange(vector& nums, int target) { // 1、遍历 int n = nums.size(); int left = -1;//左边界 int right = -1; //右边界 for ( int i = 0; i < n; ++i){ // 从左往右遍历 if (nums[i] == target){ if (left == -1){ left = i; right = i; } else{ right = i; } } } return vector{left,right}; }};

2、 二分法

class Solution {public: // 寻找第一个大于或等于 num 的位置索引, 找不到则返回数组长度 （相当于 35、搜索插入位置） int search (vector& nums, int num) { int left = 0; int right = nums.size() - 1; while (left <= right){ int mid = left + (right - left) / 2; if (nums[mid] >= target){// 大于或等于 即 左移right right = mid - 1;// 最后一个小于 num 的位置索引 } else{ // nums[mid] < target// 小于即 右移left left = mid + 1;// 第一个大于或等于 num 的位置索引 } } return left; // 寻找第一个大于或等于 num 的位置索引，返回left // 寻找最后一个小于 num 的位置索引，返回right } // 四种情况： // 1、target 小于 nums 中最小 : left = right = 0 // 2、target 大于 nums 中最大 : left = right = nums.size() // 3、target 在 nums 大小范围内，但不在其中：left = right = search(nums, target + 1) // 4、target 在 nums 数组中：left < right vector searchRange(vector& nums, int target) { int left = search(nums, target); // 寻找第一个大于或等于 target 的位置索引 int right = search(nums, target + 1); // 寻找第一个大于或等于 target+1 的位置索引 if (left < right){ return vector {left, right-1}; } return vector {-1, -1}; }};

69.x的平方根

找到满足 k 2 ≤ x k^2 ≤ x k2≤x 的最大 k k k 值，即寻找最后一个 k 2 k^2 k2小于或等于 x x x 的位置索引。

class Solution {public: // 二分查找 int mySqrt(int x) { int left = 0; int right = x; int ans = 0; while (left <= right){ int mid = left + (right - left) / 2; if ((long long)mid * mid > x){ right = mid - 1; // 寻找最后一个小于或等于 num 的位置索引 } else{ // (long long)mid * mid <= x left = mid + 1; } } return right; }};

367.有效的完全平方数

class Solution {public: bool isPerfectSquare(int num) { int left = 0; int rigth = num; while (left <= rigth){ int mid = left + (rigth - left) / 2; long square = (long) mid * mid; if (square > num){ // 二分查找条件 rigth = mid - 1; } else if (square < num){ left = mid + 1; } else{ return true; } } return false; }};