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

怠惰的未禾

发布于 2023-04-27 21:28:03

26000

代码可运行

文章被收录于专栏：Linux之越战越勇Linux之越战越勇

运行总次数：0

代码可运行

前言

这篇内容来分析分析两个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.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;
}

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){

}

2.4 思路分析

思路1：

(1)

右旋数组

k

个元素，首先想最简单的：右旋

1

个元素，把数组最后一个元素用临时变量保存起来；

(2)

其余前

n-1

个元素从后往前依次向后移动一个位置；

(3)

再把用临时变量保存起来的元素放入数组第一个位置；

(4)

重复上述操作

k

次即可。

时间复杂度

O(n*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;
    }

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

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