引言
我之前发布了关于复杂度的概念和计算,今天我带来了两道经典例题来介绍怎么使用复杂度快速解题,如果对时间复杂度和空间复杂度了解的不是很清楚的话,可以先看一下这篇博客--算法的时间复杂度和空间复杂度
1消失的数字
-- 面试题 17.04. 消失的数字 - 力扣（LeetCode）
题目描述
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1] 输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1] 输出：8
思路一:
这道题最简单的思路就是将数组进行排序在遍历一遍,可问题就出在数组排序上,如果你用冒泡排序
// 计算BubbleSort的时间复杂度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } }很明显,冒泡排序的算法时间复杂度为O(n^2),不满足题目要求
那又有人说,为何不用快排呢
void quick_sort(int q[],int l,int r) { if(l>=r) return; int x=q[(r+l)/2],i=l-1,j=r+1; while(i<j) { do i++;while(q[i]<x); do j--;while(q[j]>x); if(i<j) swap(q[i],q[j]); } quick_sort(q,l,j); quick_sort(q,j+1,r); }快排的时间复杂度为O(nlog(n)),也是大于O(n)的
所以我们一开始一定要看清楚题目的复杂度要求,对与不满足需要的思路直接pass
思路二:
求和0到n,在依次减去数组中的数,剩下的数便是缺少的那个数:
这个解法时间复杂度为O(2n),也就是O(n)
注意:这种解法在这道题没有问题,但是它存在n溢出的情况,在某些场景可能不适用.
代码1:
int missingNumber(int* nums, int numsSize){
int sum = 0;
for(int i = 0; i <= numsSize; i++)
{
sum += i;
}
for(int i = 0; i < numsSize; i++)
{
sum -= nums[i];
}
return sum;
}
思路三:
使用异或,相同的值进行异或后等于0,用x初始化为0,分别异或缺少的数组和完整的数组,留下来的便是单身狗,就是我们需要的值,有专门的题目叫单身狗,你们可以去看一下
代码二
int missingNumber(int* nums, int numsSize){
int N = numsSize;
int x = 0;
for(int i = 0; i < numsSize; i++)
{
x ^= nums[i];
}
for(int j = 0; j <= N; j++)
{
x ^= j;
}
return x;
}2旋转数组
--189. 轮转数组 - 力扣（LeetCode）
题目描述
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出:[5,6,7,1,2,3,4]解释: 向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
思路一:
循环K次,每次对数组进行一次翻转,可以使用k %= numsSize,对k的次数进行优化.
代码一
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
while(k--)
{
//旋转一次
int tmp = nums[numsSize-1];
for(int i = numsSize-2; i >= 0; i--)
{
nums[i+1] = nums[i];
}
nums[0] = tmp;
}
}注意:这个方法有一个用例没有通过:
最后一个用例数据太大,这个算法的时间复杂度为O(n^2),超出了时间限制,所以我们还得进行算法优化,寻找更优解.
思路二:
写一个逆置函数,将前n-k个逆置,在将后k个逆置,最后整体逆置,即可得到我们需要的数组,
这个算法的时间复杂度为O(n).
代码二:
void reverse(int* a, int left, int right)
{
while(left < right)
{
int tmp = a[left];
a[left] = a[right];
a[right] = tmp;
++left;
--right;
}
}
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize-1);
}3由数据范围反推算法复杂度以及算法内容
一般的算法题都会给我们数据范围,就比如翻转数组这道题,它的数据范围是:
1 <= nums.length <= 10^5我们C++代码中的操作次数控制在10^9之内,这样才不会超时,我们之前O(n^2)的算法注定过不了这道题,所以在算法题中看清数据的范围十分重要,当你熟练了之后,一般能够依靠数据范围反推算法复杂度和算法内容.
一下是在不同数据范围下，代码的时间复杂度和算法该如何选择：
小结
算法的时间复杂度是常常被忽略的一个重要因素,可以帮你快速找出最优算法,当然这也需要在一个刷题环境下慢慢训练.
