一，有序数组的平方
977. 有序数组的平方 - 力扣（LeetCode）
https://leetcode.cn/problems/squares-of-a-sorted-array/
1，直接排序
最简单的方法就是将数组nums 中的数平方后直接排序。
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> ans; for (int num: nums) { ans.push_back(num * num); } sort(ans.begin(), ans.end()); return ans; } };
复杂度分析
●时间复杂度:O(n logn),其中n是数组nums的长度。
●空间复杂度: O(logn)。 除了存储答案的数组以外，我们需要O(log n)的栈空间进行排序。
2，双指针
思路与算法
方法一没有利用[数组nums已经按照升序排序」这个条件。显然，如果数组nums中的所有数都是艳数，那么将每个数平方后，数组仍然保持升序;如果数组nums中的所有数都是负数,那么将每个数平方后，数组会保持降序。
这样一来,如果我们能够找到数组nums帧数与非负数的分界线,那么就可以用类似「归并排序」的方法了。具体地，我们设neg为数组nums中负数与非负数的分界线，也就是说，nums[0] 到nums[neg]均为负数，而nums[neg+ 1]到nums[n- 1]均为非负数。当我们将数组nums中的数平方后，那么nums[0]到nums[neg]单调递减，nums[neg+ 1]到nums[n - 1] 单调递增。
由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置neg和neg+ 1,每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时,将另一指针还未遍历到的数依次放入答案。
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); int negative = -1; for (int i = 0; i < n; ++i) { if (nums[i] < 0) { negative = i; } else { break; } } vector<int> ans; int i = negative, j = negative + 1; while (i >= 0 || j < n) { if (i < 0) { ans.push_back(nums[j] * nums[j]); ++j; } else if (j == n) { ans.push_back(nums[i] * nums[i]); --i; } else if (nums[i] * nums[i] < nums[j] * nums[j]) { ans.push_back(nums[i] * nums[i]); --i; } else { ans.push_back(nums[j] * nums[j]); ++j; } } return ans; } };
复杂度分析
●时间复杂度: O(n),中n是数组nums 的长度。
●空间复杂度: 0(1)。 除了存储答案的数组以外，我们只需要维护常量空间。
3，逆向双指针
思路与算法
同样地，我们可以使用两个指针分别指向位置 0 和n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int> ans(n); for (int i = 0, j = n - 1, pos = n - 1; i <= j;) { if (nums[i] * nums[i] > nums[j] * nums[j]) { ans[pos] = nums[i] * nums[i]; ++i; } else { ans[pos] = nums[j] * nums[j]; --j; } --pos; } return ans; } };
复杂度分析
时间复杂度：O(n)，其中 nn 是数组 nums 的长度。
空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。
二，轮转数组
189. 轮转数组 - 力扣（LeetCode）
https://leetcode.cn/problems/rotate-array/
1，使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i的元素放至新数组下标为 (i+k)mod n 的位置，最后将新数组拷贝至原数组即可。
class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); vector<int> newArr(n); for (int i = 0; i < n; ++i) { newArr[(i + k) % n] = nums[i]; } nums.assign(newArr.begin(), newArr.end()); } };
复杂度分析
- 时间复杂度： O(n)，其中 n 为数组的长度。
- 空间复杂度： O(n)。
2，数组翻转
该访法基于如下的事实:当我们将数组的元素向右移动k次后，尾部k mod n个元素会移动至数组头部，元素向后移动k mod n个位置。
该访法为数组的翻转:我们可以先将所有元素翻转，这样尾部的k mod n个元素就被移至数组头部,然后我们再翻转[0, k modn - 1]区间的元素和[k mod n,n - 1]区间的元素即能得到最后的答案。
我们以n= 7, k= 3为例进行如下展示:
class Solution { public: void reverse(vector<int>& nums, int start, int end) { while (start < end) { swap(nums[start], nums[end]); start += 1; end -= 1; } } void rotate(vector<int>& nums, int k) { k %= nums.size(); reverse(nums, 0, nums.size() - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.size() - 1); } };
复杂度分析
●时间复杂度: O(n), 其中n为数组的长度。每个元素被翻转两次，- 共n个元素，因此总时间
复杂度为O(2n)= O(n)。
●空间复杂度: 0(1)。
以上部分来自力扣，由本人整理。
