Build Array from Permutation[E,Array,Simulation]

https://leetcode.com/problems/build-array-from-permutation/

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)?

 

1. Python

 

- memory를 만들면 너무나 쉬운 답변

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        lst=[]
        for i in range(len(nums)):
            lst.append(nums[nums[i]])

        return lst

- memory를 안 만들고 할 수 있을까? -> C++ 참고

#잡기술 부리기
class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(length):
            nums.append(nums[nums[i]])
        return nums[length:]

 

2. C

 

C로는 객기 부릴게 없다

int* buildArray(int* nums, int numsSize, int* returnSize) {
        // Allocate memory for the result array
    int* ans = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;

    // Fill the result array according to the problem statement
    for (int i = 0; i < numsSize; i++) {
        ans[i] = nums[nums[i]];
    }

    return ans;
}

 

3. C++

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;i++){
            nums[i] = nums[i] + n*(nums[nums[i]]%n);
        }
        for(int i=0;i<n;i++){
            nums[i] = nums[i]/n;
        }
        return nums;
    }

};

 

되게 수학적으로 memory를 추가하지 않고, 한 list에서 old/new value를 모두 관리하는 방법이다.

 

참 .. 대단하다 진짜