void Func1(int N)
{
int count = 0;
//这是第一个部分,有两层for循环,N*N次
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
//这是第二个部分,2*N次
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
//这是第三个循环,10次--
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
2.分析时间复杂度
我们先来计算Func1函数执行了多少次代码,可以看到第一个部分里有两层循环,外层循环执行一次,内存循环就要执行N次,所以我们可以得到执行次数是N*N次;再看第二部分, 因为 for 循环里判断条件是<2*N,所以循环执行2*N次;其次第三部分 M-- 要进行10次.所以准确的次数就是 N^2+2*N+10 次,那我们这段代码的时间复杂度是这个吗,其实并不是.
假设 N 分别是 10 , 100, 1000,我们得到以下算式:
我们仔细观察,不难发现,随着 N 的增大,表达式N*N+2*N+10 表达式中 N^2 这一项的结果对整个表达式的影响是最大,从这一角度去看,我们要知道时间复杂度本质上其实是一个估算,是去看表达式中影响最大的那一项,其他项对结果的影响是微乎其微的.
// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
//计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++ k)
{
++count;
}
printf("%d\n", count);
}
//计算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;
}
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n;
while (begin < end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
// 计算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;
}
}
要求 0 ~ n 中缺失的那个,可以将 0 ~ n 的所有元素相加,得到的结果再与原数组里元素的和相减,结果就得到消失的数字.
代码如下:
int missingNumber(int* nums, int numsSize){
int misNum = 0;
for(int j = 0; j < numsSize + 1; j++)
misNum += j;
for(int i = 0; i < numsSize; i++)
misNum -= nums[i];
return misNum;
}
思路三:
异或:将数组中的数依次跟 0 ~ n 的所有数异或,最后剩下的数据就是缺的那个数字(异或:按位异或相同为 0 ,不同为 1 ).
举例如下:
我们知道相同的数异或到一起就没了,是0. 此题如果把 0 ~ n 的数与原数组里的元素进行异或,然后相同的两个数异或没了,那么剩下的就是消失的那个数,(两数组进行异或时不需要有序,因为异或满足交换律,相同的会消失,最后剩下的就是要求的数)
举例验证:
这个例子我们可以看到虽然数据没有有序,但是相同的两个数被相互消去,得到的是不同的那个数.
代码如下:
int missingNumber(int* nums, int numsSize){
int x = 0;
//用for循环求出数组中的异或之和
for(int i = 0; i < numsSize; i++)
x ^= nums[i];
for(int j = 0; j < numsSize + 1; j++)//原数组比0~n少1个数,要+1
//再和(0~n)之间的数异或
x ^= j;
return x;
}
2.题目链接：力扣--旋转数组
思路一:
如果要进行一次旋转,有数组 [1,2,3,4,5,6,7,8,9] ,可以先将数组中的最后末尾元素 9 存放到一个变量中,然后将最后一个元素之前的数据依次向后挪动,我们可以定义一个变量 end ,将它依次减减,就可以将元素依次挪动,直到最后首元素空出,再将 9 放进去,这样就完成了旋转了一次,
代码如下:
void rotate(int* nums, int numsSize, int k)
{
for(int i=0;i<k;++i )
{
//旋转一次
int tmp=0;
tmp=nums[numsSize-1];
for(int end=numsSize-2;end>=0;end--)
{
nums[end+1]=nums[end];
}
nums[0]=tmp;
}
}
当前代码的时间复杂度是O(N*K),效率太低.
思路二:
以空间换时间:创建一个新的数组，首先将后 k 个数放到新数组的前 k 项里面，然后再将剩下的数放到新数组里面，(也就是将原数组分两段存放到一个新的数组中)
最后第二个循环是将新数组的内容替换掉原数组中的内容
代码如下:
void rotate(int* nums, int numsSize, int k){
int nums1[numsSize];
for(int i=0;i<numsSize;i++)
{
nums1[(i+k)%numsSize]=nums[i];
}
for(int j=0;j<numsSize;j++)
{
nums[j]=nums1[j];
}
}
void Func1(int N)
{
int count = 0;
//这是第一个部分,有两层for循环,N*N次
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
//这是第二个部分,2*N次
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
//这是第三个循环,10次--
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
2.分析时间复杂度
我们先来计算Func1函数执行了多少次代码,可以看到第一个部分里有两层循环,外层循环执行一次,内存循环就要执行N次,所以我们可以得到执行次数是N*N次;再看第二部分, 因为 for 循环里判断条件是<2*N,所以循环执行2*N次;其次第三部分 M-- 要进行10次.所以准确的次数就是 N^2+2*N+10 次,那我们这段代码的时间复杂度是这个吗,其实并不是.
假设 N 分别是 10 , 100, 1000,我们得到以下算式:
我们仔细观察,不难发现,随着 N 的增大,表达式N*N+2*N+10 表达式中 N^2 这一项的结果对整个表达式的影响是最大,从这一角度去看,我们要知道时间复杂度本质上其实是一个估算,是去看表达式中影响最大的那一项,其他项对结果的影响是微乎其微的.
// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}
//计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++ k)
{
++count;
}
printf("%d\n", count);
}
//计算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;
}
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n;
while (begin < end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
// 计算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;
}
}
要求 0 ~ n 中缺失的那个,可以将 0 ~ n 的所有元素相加,得到的结果再与原数组里元素的和相减,结果就得到消失的数字.
代码如下:
int missingNumber(int* nums, int numsSize){
int misNum = 0;
for(int j = 0; j < numsSize + 1; j++)
misNum += j;
for(int i = 0; i < numsSize; i++)
misNum -= nums[i];
return misNum;
}
思路三:
异或:将数组中的数依次跟 0 ~ n 的所有数异或,最后剩下的数据就是缺的那个数字(异或:按位异或相同为 0 ,不同为 1 ).
举例如下:
我们知道相同的数异或到一起就没了,是0. 此题如果把 0 ~ n 的数与原数组里的元素进行异或,然后相同的两个数异或没了,那么剩下的就是消失的那个数,(两数组进行异或时不需要有序,因为异或满足交换律,相同的会消失,最后剩下的就是要求的数)
举例验证:
这个例子我们可以看到虽然数据没有有序,但是相同的两个数被相互消去,得到的是不同的那个数.
代码如下:
int missingNumber(int* nums, int numsSize){
int x = 0;
//用for循环求出数组中的异或之和
for(int i = 0; i < numsSize; i++)
x ^= nums[i];
for(int j = 0; j < numsSize + 1; j++)//原数组比0~n少1个数,要+1
//再和(0~n)之间的数异或
x ^= j;
return x;
}
2.题目链接：力扣--旋转数组
思路一:
如果要进行一次旋转,有数组 [1,2,3,4,5,6,7,8,9] ,可以先将数组中的最后末尾元素 9 存放到一个变量中,然后将最后一个元素之前的数据依次向后挪动,我们可以定义一个变量 end ,将它依次减减,就可以将元素依次挪动,直到最后首元素空出,再将 9 放进去,这样就完成了旋转了一次,
代码如下:
void rotate(int* nums, int numsSize, int k)
{
for(int i=0;i<k;++i )
{
//旋转一次
int tmp=0;
tmp=nums[numsSize-1];
for(int end=numsSize-2;end>=0;end--)
{
nums[end+1]=nums[end];
}
nums[0]=tmp;
}
}
当前代码的时间复杂度是O(N*K),效率太低.
思路二:
以空间换时间:创建一个新的数组，首先将后 k 个数放到新数组的前 k 项里面，然后再将剩下的数放到新数组里面，(也就是将原数组分两段存放到一个新的数组中)
最后第二个循环是将新数组的内容替换掉原数组中的内容
代码如下:
void rotate(int* nums, int numsSize, int k){
int nums1[numsSize];
for(int i=0;i<numsSize;i++)
{
nums1[(i+k)%numsSize]=nums[i];
}
for(int j=0;j<numsSize;j++)
{
nums[j]=nums1[j];
}
}
