-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path1920.build-array-from-permutation.cpp
More file actions
65 lines (61 loc) · 1.84 KB
/
1920.build-array-from-permutation.cpp
File metadata and controls
65 lines (61 loc) · 1.84 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// Tag: Array, Simulation
// Time: O(N)
// Space: O(1)
// Ref: -
// Note: -
// Video: https://youtu.be/M2ccKRFVX8M
// 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)?
//
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 0);
for (int i = 0; i < n; i++) {
res[i] = nums[nums[i]];
}
return res;
}
};
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
int low = nums[i];
int high = nums[nums[i]] % n;
nums[i] = high * n + low;
}
for (int i = 0; i < n; i++) {
nums[i] /= n;
}
return nums;
}
};