如何对包含n个元素的数组进行排序，其中k个元素在O（n+k log k）中不合适？

Question

我今天在一次采访中被问到这一点，我开始相信这是无法解决的

给定一个大小为n的排序数组，选择数组中的k元素，并将它们重新排列回数组中，生成一个新的“nk排序”数组

查找在新数组中移动的k（或更少）个元素

下面是创建此类数组的（Python）代码，但我不关心用于此的语言

import numpy as np


def __generate_unsorted_array(size, is_integer=False, max_int_value=100000):
    return np.random.randint(max_int_value, size=size) if is_integer else np.random.rand(size)


def generate_nk_unsorted_array(n, k, is_integer=False, max_int_value=100000):
    assert k <= n
    unsorted_n_array = __generate_unsorted_array(n - k, is_integer, max_int_value=max_int_value)
    sorted_n_array = sorted(unsorted_n_array)
    random_k_array = __generate_unsorted_array(k, is_integer, max_int_value=max_int_value)
    insertion_inds = np.random.choice(n - k + 1, k, replace=True)  # can put two unsorted next to each other.
    nk_unsorted_array = np.insert(sorted_n_array, insertion_inds, random_k_array)
    return list(nk_unsorted_array)

这在复杂性约束下可行吗

这只是问题的一部分。对O(n+klogk)中的“nk排序数组”进行排序所需的整个问题

Answer 1

即使@Gulzar's solution是正确的，它实际上并没有给我们O(n + k * log k)。 问题出在sort_nk_unsorted_list函数中。不幸的是，从Python列表中删除任意项不是固定时间It's actually ^{}。这使得整个算法的复杂度为O(n + nk + k * log k)

要解决这个问题，我们可以使用不同的数据结构。如果使用双链接列表，则从该列表中删除项目实际上是O(1)。不幸的是，Python在默认情况下没有附带一个

这是我的解决方案，它实现了O(n + k * log k)

解决问题的入口点函数：

def sort(my_list):
    in_order, out_of_order = separate_in_order_from_out_of_order(my_list)

    out_of_order.sort()

    return merge(in_order, out_of_order)

将有序元素与无序元素分开的函数：

def separate_in_order_from_out_of_order(my_list):
    list_dll = DoublyLinkedList.from_list(my_list)
    out_of_order = []
    
    current = list_dll.head

    while current.next is not None:
        if current.value > current.next.value:
            out_of_order.append(current.value)
            out_of_order.append(current.next.value)

            previous = current.prev

            current.next.remove()
            current.remove()

            current = previous
        else:
            current = current.next

    in_order = list_dll.to_list()

    return in_order, out_of_order

合并两个单独列表的函数：

def merge(first, second):
    """
    Merges two [sorted] lists into a sorted list.

    Runtime complexity: O(n)
    Space complexity: O(n)
    """
    i, j = 0, 0

    result = []
    
    while i < len(first) and j < len(second):
        if first[i] < second[j]:
            result.append(first[i])
            i += 1            
        else:
            result.append(second[j])
            j += 1            

    result.extend(first[i:len(first)])
    result.extend(second[j:len(second)])

    return result

最后，这是DoublyLinkedList实现（我使用了sentinel节点使事情变得更简单）：

class DoublyLinkedNode:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

    def remove(self):
        if self.prev:
            self.prev.next = self.next

        if self.next:
            self.next.prev = self.prev
        

class DoublyLinkedList:
    def __init__(self, head):
        self.head = head

    @staticmethod
    def from_list(lst):
        sentinel = DoublyLinkedNode(-math.inf)
        previous = sentinel

        for item in lst:
            node = DoublyLinkedNode(item)
            node.prev = previous
            previous.next = node

            previous = node
        
        return DoublyLinkedList(sentinel)

    def to_list(self):
        result = []
        current = self.head.next

        while current is not None:
            result.append(current.value)
            current = current.next

        return result

以下是我用来验证代码的单元测试：

import unittest


class TestSort(unittest.TestCase):
    def test_sort(self):
        test_cases = [
            # ( input, expected result)
            ([1, 2, 3, 4, 10, 5, 6], [1, 2, 3, 4, 5, 6, 10]),
            
            ([1, 2, 5, 4, 10, 6, 0], [0, 1, 2, 4, 5, 6, 10]),

            ([1], [1]),

            ([1, 3, 2], [1, 2, 3]),
            ([], [])
        ]

        for (test_input, expected) in test_cases:
            result = sort(test_input)
        
            self.assertEqual(expected, result)

Answer 2

注意：这是一个概念性的解决方案。它是用Python编码的，但由于Python实现List的方式，实际上并没有以所需的复杂度运行。请参见soyuzzzz's answer以查看复杂性需求中Python的实际解决方案

接受了@Soyuzzz的回答

原始答案（可行，但复杂度仅在假设Python列表的链表实现时正确，事实并非如此）：

这将对O(n + klogk)中的nk未排序数组进行排序，假设该数组应该是升序的

1. 通过遍历数组查找未排序的元素
2. 如果找到了这样一个元素（它比下面的元素大），那么它或者下面的元素（或者两者）都不正常
3. 将它们放在一边，并将它们从阵列中移除
4. 继续遍历新获得的数组（删除后），形成位于找到的元素之前的索引
5. 这将在O(n)时间内保留2k个元素
6. 排序2k元素O(klogk)
7. 合并两个总有n个元素的排序列表，O(n)
8. 总计O(n + klogk)

代码：

def merge_sorted_lists(la, lb):
    if la is None or la == []:
        return lb
    if lb is None or lb == []:
        return la
    a_ind = b_ind = 0
    a_len = len(la)
    b_len = len(lb)

    merged = []
    while a_ind < a_len and b_ind < b_len:
        a_value = la[a_ind]
        b_value = lb[b_ind]

        if a_value < b_value:
            merged.append(la[a_ind])
            a_ind += 1
        else:
            merged.append(lb[b_ind])
            b_ind += 1

    # get the leftovers into merged
    while a_ind < a_len:
        merged.append(la[a_ind])
        a_ind += 1
    while b_ind < b_len:
        merged.append(lb[b_ind])
        b_ind += 1

    return merged

及

def sort_nk_unsorted_list(nk_unsorted_list):
    working_copy = nk_unsorted_list.copy()  # just for ease of testing

    requires_resorting = []

    current_list_length = len(working_copy)
    i = 0
    while i < current_list_length - 1 and 1 < current_list_length:
        if i == -1:
            i = 0

        first = working_copy[i]
        second = working_copy[i + 1]

        if second < first:
            requires_resorting.append(first)
            requires_resorting.append(second)

            del working_copy[i + 1]
            del working_copy[i]
            i -= 2
            current_list_length -= 2
        i += 1

    sorted_2k_elements = sorted(requires_resorting)
    sorted_nk_list = merge_sorted_lists(sorted_2k_elements, working_copy)
    return sorted_nk_list