Given a zero-based permutation nums
(0-indexed), build an array ans
of the same length where ans[i] = nums[nums[i]]
for each 0 <= i < nums.length
and return it.
A zero-based permutation nums
is an array of distinct integers from 0
to nums.length - 1
(inclusive).
Example 1:
Input: nums = [0,2,1,5,3,4] Output: [0,1,2,4,5,3] Explanation: The array ans is built as follows: ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]] = [0,1,2,4,5,3]
Example 2:
Input: nums = [5,0,1,2,3,4] Output: [4,5,0,1,2,3] Explanation: The array ans is built as follows: ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]] = [4,5,0,1,2,3]
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] < nums.length
- The elements in
nums
are distinct.
Follow-up: Can you solve it without using an extra space (i.e., O(1)
memory)?
Solution 1: Straight forward
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: vector<int> buildArray(vector<int>& nums) { vector<int> ans(nums); for (size_t i = 0; i < nums.size(); ++i) ans[i] = nums[nums[i]]; return ans; } }; |
Solution 2: Follow up: Inplace Encoding
Since nums[i] <= 1000, we can use low 16 bit to store the original value and high 16 bit for new value.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: vector<int> buildArray(vector<int>& nums) { const int n = nums.size(); for (int i = 0; i < n; ++i) nums[i] |= (nums[nums[i]] & 0xffff) << 16; for (int i = 0; i < n; ++i) nums[i] >>= 16; return nums; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment