【数据结构】时间复杂度和空间复杂度以及相关OJ题的详解分析(下)

简介: 【数据结构】时间复杂度和空间复杂度以及相关OJ题的详解分析(下)

3.根据对时间复杂度的要求编写代码

3.1 消失的数字

17.04. 消失的数字

题述:数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

示例 1: ---------- 示例 2:

输入:[3,0,1] ----- 输入:[9,6,4,2,3,5,7,0,1]

输出:2 ----------- 输出:8


核心思想:

方法一:先排序,再依次判断第1个数和之后的数相加是否等于第3个数,若不等,则它们的和就是缺失的数————冒泡排序时间复杂度O(N²),快速排序时间复杂度O(N*log₂N)

方法二:求和,如果有n个数,则0+1+2…+n,最后整体再减去数组中的值的累加就是缺失的数————时间复杂度O(N)

方法三:异或,使用0跟0—n之间的数异或,再跟数值中的值异或,异或的结果就是缺失的数

方法二

IO型:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int FindNum1(int arr[], int n)
{
  int i = 0;
  //把n+1个数加起来,放在sum里
  int sum = 0;
  for (i = 0; i < n + 1; i++)
  {
    sum += i;
  }
  //再减去数组里的数,结果就是缺失的数
  for (i = 0; i < n; i++)
  {
    sum -= arr[i];
  }
  return sum;
}
int main()
{
  int arr[20] = { 0 };
  //规定输入有n个数
  int n = 3;
  int i = 0;
  for (i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  int ret = FindNum1(arr, n);
  printf("%d\n", ret);
  return 0;
}

方法三

IO型:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int FindNum2(int arr[], int n)
{
  int i = 0;
  //把n+1个数异或后,放在sum里
  int val = 0;
  for (i = 0; i < n + 1; i++)
  {
    val ^= i;
  }
  //再和数组里的异或,剩下的就是缺失的数
  for (i = 0; i < n; i++)
  {
    val ^= arr[i];
  }
  return val;
}
int main()
{
  int arr[20] = { 0 };
  //n个数
  int n = 3;
  int i = 0;
  for (i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }
  int ret = FindNum2(arr, n);
  printf("%d\n", ret);
  return 0;
}

接口型:

int missingNumber(int* nums, int numsSize)
{
    int x=0;
    for(int i=0;i<numsSize;i++)
    {
        x^=nums[i];
    }
    for(int j=0;j<numsSize+1;++j)
    {
        x^=j;
    }
    return x;
}

12c4ff489e394f57b8851901c2dac62e.png

3.2 轮转数组

189. 轮转数组

题述:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。要求时间复杂度O(N)

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

核心思想:

方法一:这是1个字符的旋转,拷贝一份最右值,数组中的值都向右挪劫1次,再把拷贝的内容放在开头;在外面套一层循环就可以旋转k个字符了————时间复杂度O(N²)

分析:O(k*N)最坏情况下 k为N-1或N-1的倍数->O(N²)

方法二:空间换时间————时间复杂度O(N),空间复杂度O(N)

方法三:三步翻转法————时间复杂度O(N),空间复杂度O(N)–调用一个栈帧


方法二

IO型:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<assert.h>
char* Rotate1(const char* arr, int len, int k, char* temp)
{
  assert(arr && temp);
  //拷贝一份新空间的首地址用于返回
  char* tem = temp;
  //我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr,所以如果k大于arr时,我们需要看看k有几个arr,并把它排除掉
  k %= len;
  int i = 0;
  //先拷贝后半部分的字符
  for (i = len - k; i < len; i++)
  {
    *temp = *(arr + i);
    temp++;
  }
  //再拷贝前半部分的字符
  for (i = 0; i < len - k; i++)
  {
    *temp = *(arr + i);
    temp++;
  }
  return tem;
}
int main()
{
  //temp为新的空间
  char temp[20] = { 0 };
  //arr存储要旋转的字符串
  char arr[20] = { 0 };
  gets(arr);
  //旋转k个字符
  int k = 0;
  scanf("%d", &k);
  char* ret = Rotate1(arr, strlen(arr), k, temp);
  printf("%s\n", ret);
  return 0;
}

接口型:

void rotate(int* nums, int numsSize, int k)
{
    if(k>numsSize)
        k%=numsSize;
    int *tmp=(int*)malloc(sizeof(int)*numsSize);
    memcpy(tmp,nums+numsSize-k,sizeof(int)*k);
    memcpy(tmp+k,nums,sizeof(int)*(numsSize-k));
    memcpy(nums,tmp,sizeof(int)*(numsSize));
    free(tmp);
    tmp=NULL;
}

8372da36a55c42c581c795d331e2ba03.png方法三

IO型:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<string.h>
void reverse(char* left, char* right)
{
  assert(left && right);
  while (left < right)
  {
    char temp = *left;
    *left = *right;
    *right = temp;
    left++;
    right--;
  }
}
void string_right_rotation(char* str, int k)
{
  assert(str);
  int len = strlen(str);
  //我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr,所以如果k大于arr时,我们需要看看k有几个arr,并把它排除掉
  k %= len;
  reverse(str, str + (len - k - 1));//第一部分
  reverse(str + (len - k), str + len - 1);//第二部分
  reverse(str, str + len - 1);//整体
}
int main()
{
  //arr存储要旋转的字符串
  char arr[20] = { 0 };
  gets(arr);
  //旋转k个字符
  int k = 0;
  scanf("%d", &k);
  string_right_rotation(arr, k);
  printf("%s\n", arr);
  return 0;
}

接口型:

void reverse(int*nums,int begin, int end)
{
    while(begin<end)
    {
        int tmp=nums[begin];
        nums[begin]=nums[end];
        nums[end]=tmp;
        ++begin;
        --end;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    if(k>numsSize)
        k%=numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

45a9864b95c04d888cac378859012459.png

4.空间复杂度

4.1 什么是空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间,因为没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。

注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

4.2 常见的空间复杂度计算举例

4.2.1 实例1:

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;
  }
} 

分析:

相比时间复杂度来说:时间是累计的,但空间不是累计的(可以重复利用)//end、exchange、i 额外的空间

BubbleSort的空间复杂度为F(N) = (3)

使用大O渐近表示法:O(1)

4.2.2 实例2:

long long* Fibonacci(size_t n) 
{
  if(n==0)
    return NULL;
  long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
  fibArray[0] = 0;
  fibArray[1] = 1;
  for (int i = 2; i <= n ; ++i)
  {
    fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
  }
  return fibArray;
 }

分析:malloc((n+1)

使用大O渐近表示法:O(N)

4.2.3 实例3:

long long Fac(size_t N)
{
  if(N == 1)
    return 1;
  return Fac(N-1)*N;
}

分析:Fac(N)->Fac(N-1)->.……->Fac(1)建立N个栈帧

使用大O渐近表示法:O(N)

4.2.4 实例4:

long long Fib(size_t N) 
{
  if(N < 3)
    return 1;
  return Fib(N-1) + Fib(N-2);
}
• 1
• 2
• 3
• 4
• 5
• 6

//VS2019->窗口->调用堆栈->双击看内存的变量

分析:栈帧销毁了可重复利用,所以递归算法的空间复杂度取决于每次调用的空间复杂度和最大递归深度:Fib(N)->Fib(N-1)->.……->Fib(1)

使用大O渐近表示法:O(N)

5.根据对空间复杂度的要求编写代码

5.1 移除元素

27. 移除元素

题述:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,必须仅使用O(1) 额外空间并 原地 修改输入数组。


示例 1:

输入:nums = [3,2,2,3], val = 3

输出:2, nums = [2,2]

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2

输出:5, nums = [0,1,4,0,3]


提示:

0 <= nums.length <= 100

0 <= nums[i] <= 50

0 <= val <= 100

接口型:

int removeElement(int* nums, int numsSize, int val)
{
    int dest=0,src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[dest]=nums[src];
            dest++;
        }
        src++;
    }
    return dest;
}

86a3214010ae47e2bd97f7d91e4b525e.png

6.总结:

今天我们认识并学习了时间复杂度和空间复杂度的相关概念,通过实例进行了分析,和一些OJ题举例。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

c3ad96b16d2e46119dd2b9357f295e3f.jpg

相关文章
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
28 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
2月前
|
机器学习/深度学习 存储 算法
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
|
2月前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
15 0
|
5月前
|
存储 索引
【数据结构OJ题】设计循环队列
力扣题目——设计循环队列
38 1
【数据结构OJ题】设计循环队列
|
4月前
|
存储 算法
【数据结构】——时间复杂度与空间复杂度
【数据结构】——时间复杂度与空间复杂度
|
24天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
114 9
|
15天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
22 1
|
2天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
20 5
|
18天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。

热门文章

最新文章

下一篇
无影云桌面