复杂度练习

旋转数组

消失的数字

**

1.旋转数组

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

示例 2:

输入：nums = [-1,-100,3,99], k = 2

输出：[3,99,-1,-100]

解释:

向右轮转 1 步: [99,-1,-100,3]

向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105

-231 <= nums[i] <= 231 - 1

0 <= k <= 105

**

思路一：

1.前n-k个元素逆置

2.后k个元素逆置

3.最后进行整体的逆置

void reverse(int* nums, int left, int right)
{
    while (left< right)
    {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        ++left;
        --right;
    }
}
 if (k > numsSize)
    {
        k %= numsSize;
    }
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}

复杂度分析

时间复杂度：O(n)O(n)，其中 nn 为数组的长度。每个元素被翻转两次，一共 nn 个元素，因此：

总时间复杂度为 O(2n)=O(n)O(2n)=O(n)。

空间复杂度：O(1)O(1)。

思路二：

1.先创建一个新的数组

2.把后k个数放到新数组

3.在把前k个数向后移动

void rotate(int* nums, int numsSize, int k)
{
     k %= numsSize;  //变长数组
     int temp = nums[numsSize];
     //把后k个元素拷贝到前面
      int j=0;
      for(int i= numsSize - k; i<numsSize ; i++)
        {
            temp[j] = nums[i];
            ++j;
        }
        //把前n-k个拷贝到后面
        for(int i= 0; i<numsSize-k ; i++)
        {
            temp[j] = nums[i];
            ++j;
        }
        //拷贝回去
        for(int i= 0; i<numsSize ; i++)
        {
                temp[] = nums[i];     
         }
 }

这里使用malloc来创建新数组的话也可以，只是不能调试而已

复杂度分析

空间复杂度： O(n)

时间复杂度： O(n)O(n)，其中 nn 为数组的长度

**

2.消失的数字

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

示例 1：

输入：[3,0,1]

输出：2

示例 2：

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

输出：8

思路一：

数学

将从 0 到 n的全部整数之和先计算出来，接着我们去遍历数组，用得到的和减去数组中的元素，便可得到我们需要的数

int missingNumber(int* nums, int numsSize){
         int n=numsSize;
         int ret=n*(n+1)/2;
         for(int i=0; i<numsSize; i++)
         {
             ret-=nums[i];
         }
        return ret;

复杂度分析

时间复杂度：O(n)，其中 n是数组 nums 的长度。需要 O(1)的时间计算从 0 到 nn的全部整数之和以及需要 O(n) 的时间计算数组 nums 的元素之和。

空间复杂度：O(1)

思路二：

数组 nums 中有 n个数，在这 n个数的后面添加从 0 到 n 的每个整数，则添加了 n+1个整数，共有 2n+1个整数。

在 2n+1 个整数中，消失的数字只在后面 n+1 个整数中出现一次，其余的数字在前面 n 个整数中（即数组中）和后面 n+1个整数中各出现一次，即其余的数字都出现了两次。

根据出现的次数的奇偶性，可以使用按位异或运算得到消失的数字。按位异或运算 \oplus⊕ 满足交换律和结合律，且对任意整数x 都满足 x⊕x=0 和 x⊕0=x。

由于上述 2n+12n+1 个整数中，消失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+1个整数进行按位异或运算，结果即为消失的数字

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

复杂度分析：

时间复杂度：O(n)，其中 n是数组 nums 的长度。需要对 2n+1个数字计算按位异或的结果。

空间复杂度：O(1)

**