Build Array from Permutation

2023-01-16

Arrays

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

1
2
3
4
5
6
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]

Source: Leetcode

Solution

Python solution

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

"""
floor division 11//3 #3
modulo 11%3  #2
"""

import time

def buildArray(nums):
   q = len(nums)
   print(q)
   for i,c in enumerate(nums):
       nums[i] += q * (nums[c] % q)
   print(nums)
   for i,_ in enumerate(nums):
       # floor division
       nums[i] //= q
   return nums


num_list = [0,2,1,5,3,4]
start = time.process_time()
print(buildArray(num_list))

print(f"Task took {time.process_time() - start}")

Golang Solution

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

package main

import (
	"fmt"
	"log"
	"time"
)

func buildArray(nums []int) []int {
	q := len(nums)
	for i, s := range nums {
		nums[i] += q * (nums[s] % q)

	}
	fmt.Println(nums)
	for i, _ := range nums {
		// note nums[i]/q already does floor division since there are integers
		nums[i] = nums[i] / q

	}
	return nums

}

// Main function
func main() {

	start := time.Now()

	arr2 := []int{0, 2, 1, 5, 3, 4}
	ans := buildArray(arr2)
	fmt.Println(ans)

	elapsed := time.Since(start)
	log.Printf("Task took %s", elapsed)
}