Absolute Permutation（绝对置换）

Problem Link

Problem Description

额外写了一个swap方法用于交换数组中的两个元素
2*k为一组进行两两交换,故长度n需为2k的倍数

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会出现timeout,参考讨论区的提示改写为以下的版本后全部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