【初阶数据结构】复杂度算法题篇

半截诗

发布于 2024-10-09 18:47:16

1340

文章被收录于专栏：学西学西

旋转数组

力扣原题

方案一

循环K次将数组所有元素向后移动⼀位（代码不通过)

时间复杂度O(n2) 空间复杂度O(1)

void rotate(int* nums, int numsSize, int k) {
    while (k--) {
        int end = nums[numsSize - 1];
        for (int i = numsSize - 1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        nums[0] = end;
    }
}

时间复杂度过高，需要优化

方案二

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

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

void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i) {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = newArr[i];
    }
}

记得最后要把新数组数据复制到原数组
时间复杂度降低了，可以通过
空间复杂度提升，仍可以优化

方案三

数组翻转

该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。
我们可以先将所有元素翻转，这样尾部的 kmodn 个元素就被移至数组头部，然后我们再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案
时间复杂度：O(n) 空间复杂度：O(1)

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) {
    k = k % numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-27，如有侵权请联系 cloudcommunity@tencent.com 删除

算法