以特定顺序排列数组中的元素

Ambidextrous 发表于 Dev

灵巧的

在Careercup上找到此面试问题

给定一个具有n个整数的数组A。重新排列数组，使A [0] <= A [1]> = A [2] <= A [3]> = A [4] <= A [5]，依此类推

编辑：数组未排序，您必须在线性时间O（N）中进行操作

我无法在线性时间内找到解决方案，我得到的最接近的是对数组进行排序，然后重新排列元素。有人知道如何在线性时间内完成吗？甚至可以在线性时间内完成吗？

我提出的解决方案是按nlogn的时间对数组进行排序，然后用i-1和i + 1重新排列每个奇数元素i。

卢卡·安格莱蒂（Luca Angeletti）

您可以使用此函数（代码在Swift中）在时间O（n）中以Wave形式排列数组。

func wave(inout list: [Int]) {
    let evenIndexes = (0..<list.count).filter { $0 % 2 == 0 }

    for index in evenIndexes {
        if index > 0 && list[index] > list[index-1] {
            swap(&list[index], &list[index-1])
        }

        if index < list.count - 1 && list[index] > list[index+1] {
            swap(&list[index], &list[index+1])
        }
    }
}

此解决方案基于此处描述的算法。

测试

var test0 = [1,2,3,4,5,6]
wave(&test0)
print(test0) // [1, 3, 2, 5, 4, 6]

var test1 = [4, 6, 2, 1, 3, 7]
wave(&test1)
print(test1) // [4, 6, 1, 3, 2, 7]

var test2 = [20, 9, 4, 2, 0]
wave(&test2)
print(test2) // [9, 20, 2, 4, 0]

时间复杂度

该函数已for loop执行n / 2次（仅对于偶数索引）。因此for循环具有时间复杂性O(n)。

在内部，for loop我们找到了两个if then语句，它们都是在常量时间内执行的O(1)。

因此，时间复杂度是O(n) * O(1) = O(n)其中n是输入数组中元素的数量。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。

编辑于 2020-11-2

我来说两句

0 条评论

登录后参与评论