如何对具有n个元素的数组进行排序，其中k个元素在O(n + k log k)中不适当? [英] How to sort an array with n elements in which k elements are out of place in O(n + k log k)?

问题描述

今天在一次采访中有人问我这个问题，并且开始认为这无法解决.

I was asked this in an interview today, and am starting to believe it is not solvable.

给出大小为 n 的排序数组，在​​该数组中选择 k 个元素，然后将它们重新洗回到数组中，从而得到一个新的"nk-sorted"元素.数组.

Given a sorted array of size n, select k elements in the array, and reshuffle them back into the array, resulting in a new "nk-sorted" array.

查找在该新数组中移动的k个(或更少)元素.

Find the k (or less) elements that have moved in that new array.

这里是创建此类数组的(Python)代码，但我不在乎此语言.

Here is (Python) code that creates such arrays, but I don't care about language for this.

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)

这在复杂性约束下可行吗?

Is this doable under the complexity constraint?

这只是问题的一部分.排序"nk-sorted array"所需的整个问题都没有.在 O(n + klogk)

This is only part of the question. The whole question required to sort the "nk-sorted array" in O(n+klogk)

推荐答案

尽管@Gulzar的解决方案是正确的，但实际上并没有给我们 O(n + k * log k).问题出在 sort_nk_unsorted_list 函数中.不幸的是，从Python列表中删除任意项并不是固定的时间.实际上是 O(n) .这使整个算法的复杂度为 O(n + nk + k * log k)

Even though @Gulzar's solution is correct, it doesn't actually give us O(n + k * log k). The problem is in the sort_nk_unsorted_list function. Unfortunately, deleting an arbitrary item from a Python list is not constant time. It's actually O(n). That gives the overall algorithm a complexity of O(n + nk + k * log k)

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

What we can do to address this is use a different data structure. If you use a doubly-linked list, removing an item from that list is actually O(1). Unfortunately, Python does not come with one by default.

这是我的解决方案，可以实现 O(n + k * log k).

Here's my solution that achieves O(n + k * log k).

解决问题的入口函数:

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

    out_of_order.sort()

    return merge(in_order, out_of_order)

将有序元素与无序元素分开的功能:

The function that separates the in-order elements from the out-of-order elements:

def separate_in_order_from_out_of_order(list):
    list_dll = DoublyLinkedList.from_list(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

合并两个分开的列表的功能:

The function to merge the two separated lists:

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实现(我使用了哨兵节点使事情变得更容易):

And last, this is the DoublyLinkedList implementation (I used a sentinel node to make things easier):

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

这些是我用来验证代码的单元测试:

And these are the unit tests I used to validate the code:

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)

这篇关于如何对具有n个元素的数组进行排序，其中k个元素在O(n + k log k)中不适当?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！