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

核心思想：

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

方法二：求和，如果有n个数，则０＋１＋２…＋ｎ，最后整体再减去数组中的值的累加就是缺失的数————时间复杂度O(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;
}

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]

核心思想：

方法一：这是１个字符的旋转，拷贝一份最右值，数组中的值都向右挪劫１次，再把拷贝的内容放在开头；在外面套一层循环就可以旋转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;
}

方法三

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

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) = (３)

使用大O渐近表示法：O(１)

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