今天在一次采访中有人问我这个问题，并且开始认为这无法解决.
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)中不适当?
发布评论