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

旋转数组

力扣原题

---

方案一

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

时间复杂度O(n²)
空间复杂度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);
}