数据结构初步（二）- oj练习-时间与空间复杂度

前言

这篇内容来分析分析两个oj题。

---

1. 消失的数字

1.1 oj链接

力扣链接：消失的数字

---

1.2 题目与要求

数组$nums$包含从$0$到$n$的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在$O(n)$时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：$[3,0,1]$
输出：$2$
示例 2：
输入：$[9,6,4,2,3,5,7,0,1]$
输出：$8$

1.3 题目所给的C语言代码框架

int missingNumber(int* nums, int numsSize){

}
1
2
3

---

1.4 思路分析

$(1)$已知数组中$nums$只缺了一个数，先计算出数组不缺这一个数时的所有数的和$sum1$；
$(2)$遍历数组$nums$，计算数组实际所有数的和$sum2$;
$(3)$二者的差值$sum1-sum2$就是所缺的那个数。

时间复杂度$O(n)$
空间复杂度$O(1)$

---

1.5 代码实现

int missingNumber(int* nums, int numsSize){
    int sum1 = (numsSize*numsSize+numsSize)/2;
    int sum2 = 0;
    for(int i=0; i<numsSize; ++i){
        sum2 += nums[i];
    }
    return sum1 - sum2;
}
1
2
3
4
5
6
7
8

---

2. 轮转数组

2.1 oj链接

力扣链接：轮转数组

---

2.2 题目与要求

给你一个数组，将数组中的元素向右轮转 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]$

提示：
$1<=nums.length<=105$
$-231<=nums[i]<=231-1$
$0<=k<=105$
进阶：
尽可能想出更多的解决方案，至少有三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 $O(1)$ 的 原地 算法解决这个问题吗？

---

2.3 C语言代码框架

void rotate(int* nums, int numsSize, int k){

}
1
2
3

---

2.4 思路分析

思路1：

$(1)$右旋数组$k$个元素，首先想最简单的：右旋$1$个元素，把数组最后一个元素用临时变量保存起来；
$(2)$其余前$n-1$个元素从后往前依次向后移动一个位置；
$(3)$再把用临时变量保存起来的元素放入数组第一个位置；
$(4)$重复上述操作$k$次即可。

时间复杂度$O(n\ast k)$，当$k$足够大时也最多只能有效右旋$n-1$个元素，时间复杂度是$O(n^2)$
空间复杂度$O(1)$

---

思路2：

$(1)$以空间换时间的思想，临时创建一个与数组$nums$大小相同的数组；
$(2)$原数组需要右旋的后$k$个元素，相对顺序不变的放入临时数组的前$k$个位置；原数组前$n-k$个元素相对顺序不变的放入新临时数组的后$n-k$个位置；
$(4)$把临时数组的所有元素依次移动到元数组对应位置即可。

时间复杂度$O(n)$
空间复杂度$O(n)$

---

思路3：

这种思路比较难想，但确实非常好用。
$(1)$首先，逆置数组的前$n-k$个不需要右旋的的元素；
$(2)$然后，逆置数组后$k$个需要右旋的元素；
$(3)$最后，逆置整个数组的元素。

时间复杂度$o(n)$
空间复杂度$O(1)$

---

2.5 代码实现

思路1：

//思路1
    k %= numsSize;
    while(k--){
        int tmp = nums[numsSize-1];
        for(int i=numsSize-1; i>0; --i){
            nums[i] =nums[i-1];
        }
        nums[0] = tmp;
    }
1
2
3
4
5
6
7
8
9

思路2：

void rotate(int* nums, int numsSize, int k){
    //思路2：空间换时间
    k %= numsSize;
    int *arr = (int*)malloc(sizeof(int) * numsSize);
    int i=0;
    for(int j=numsSize-k; j<numsSize; ++j,++i){
        arr[i] = nums[j];
    }
    for(int j=0; j<numsSize-k; ++j,++i){
        arr[i] = nums[j];
    }
    for(i=0;  i<numsSize; ++i){
        nums[i] =arr[i];
    }
    free(arr);
    arr = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路3：

void reverse(int* nums, int left, int right){
    while(left < right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    //思路3：原地交换
    k %= numsSize;
    reverse(nums, 0, numsSize-k-1);
    reverse(nums, numsSize-k, numsSize-1);
    reverse(nums, 0, numsSize-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

结语

本文到这里就算是结束了，感谢看到这里的你！

---

$END$