Absolute Permutation（絕對置換）

Problem Link

Problem Description

額外寫了一個(gè)swap方法用于交換數(shù)組中的兩個(gè)元素
2*k為一組進(jìn)行兩兩交換,故長度n需為2k的倍數(shù)

Function Description

Complete the absolutePermutation function in the editor below. It should return an integer that represents the smallest lexicographically smallest permutation, or -1 if there is none.
absolutePermutation has the following parameter(s):

• n: the upper bound of natural numbers to consider, inclusive
• k: the integer difference between each element and its index

Solution

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
    return arr

def absolutePermutation(n, k):
    count = list(range(1, n+1))
    index = list(range(1, n+1))

    if k == 0 :
        return index
    if (k != 0 and n % 2 != 0) or (2 * k > n) or (n % (2 * k) != 0):
        return [-1]

    for i in range(n):
        for j in range(i+1, n):
            if index[i] in count and index[i] + k == index[j]:
                index = swap(index, i, j)
                count.remove(index[i])
                count.remove(index[j])
    if not count:
        return index
    else:
        return [-1]

這種寫法總是有一半的testcase會出現(xiàn)timeout,參考討論區(qū)的提示改寫為以下的版本后全部testcase順利通過

def absolutePermutation(n, k):
    index = list(range(1, n + 1))

    if k == 0:
        return index
    if (k != 0 and n % 2 != 0) or (2 * k > n) or (n % (2 * k) != 0):
        return [-1]
    
    group = n // (2 * k)
    for i in range(group):
        ind = i*2*k
        for j in range(k):
            index = swap(index, ind+j, ind+j+k)
    return index