问题描述
今天在一次采访中有人问我这个问题，并且开始认为这无法解决.
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)中不适当?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！