14

面接でわからない質問があります。サイズ N の配列が与えられた場合、サブセット内の要素が互いに最も離れているようなサイズ k のサブセットを見つけます。つまり、要素間のペアごとの最小距離を最大化します。

Example:

Array = [1,2,6,10]
k = 3

answer = [1,6,10]

ブルートフォースの方法では、実行時に指数関数的であるサイズ k のすべてのサブセットを見つける必要があります。

私が持っていた 1 つのアイデアは、配列から等間隔に値を取得することでした。これが意味することは

  1. 最初と最後の要素を取る
  2. それらの差（この場合は10-1）を見つけ、それをkで割ります（（10-1）/ 3 = 3）
  3. 両端から 2 つのポインターを内側に移動し、前の選択から +/- 3 の要素を選択します。この場合、1 と 10 から始めて、4 と 7 に最も近い要素を見つけます。それは 6 になります。

これは、エレメントをできるだけ均等に配置する必要があるという直感に基づいています。それが機能する/機能しないことを証明する方法がわかりません。誰かが方法を知っているか、より良いアルゴリズムを持っている場合は、共有してください。ありがとう！

4

5 に答える 5

7

これは、DP を使用して多項式時間で解くことができます。

最初のステップは、あなたが述べたように、リスト A をソートすることです。 X[i,j] を、最初の i 個の要素 A から j 個の要素を選択するための解とします。

ここで、X[i+1, j+1] = max( min( X[k,j], A[i+1]-A[k] ) ) 以上 k<=i.

初期化ステップとサブセットステップの記憶はあなたに任せます。

あなたの例 (1,2,6,10) では、次のように動作します。

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1
于 2012-09-05T11:38:51.253 に答える
2

基本的な考え方は正しいと思います。配列を並べ替えることから始め、最初と最後の要素を取得して、残りを決定する必要があります。

これを解決するための多項式アルゴリズムを考えることができないので、2つのオプションのいずれかを提案します。

1つは、検索アルゴリズム、分枝限定法を使用することです。これは、優れたヒューリスティックが手元にあるためです。ソリューションの上限は、これまでに選択した要素間のギャップの最小サイズであるため、最初の推測（均等に間隔を空けたセル）は、適切なベースラインを提供し、ほとんどのブランチをすぐに削除するのに役立ちます。k最悪の場合のパフォーマンスはですが、これは、の値が小さい場合は正常に機能しますO(N^k)。

もう1つのオプションは、同じベースラインから開始し、そのベースラインの最小ペアワイズ距離を計算してから、それを改善することです。最小距離が10のサブセットがあるとし、11のサブセットを取得してみます。これは欲張りアルゴリズムで簡単に実行できます。ソートされたシーケンスの最初のアイテムを選択して、前のアイテムとの距離が大きくなるようにします。 -または-必要な距離に等しい。成功した場合はさらに増やしてみてください。失敗した場合は、そのようなサブセットはありません。

後者のソリューションは、配列が大きく、k比較的大きい場合に高速になりますが、配列内の要素は比較的小さくなります。それらが何らかの値に拘束されている場合M、このアルゴリズムにはO(N*M)時間がかかります。または、わずかな改善O(N*log(M))がありますが、ここで、Nは配列のサイズです。

Evgeny Kluevが彼の回答で示唆しているように、最大​​ペアワイズ距離にも適切な上限があり、これらのアルゴリズムのいずれかで使用できます。したがって、後者の複雑さは実際にはO(N*log(M/k))です。

于 2012-09-05T10:55:45.617 に答える
0

あなたのセットは注文されたと思います。そうでない場合、私の答えは少し変更されます。

Let's suppose you have an array X = (X1, X2, ..., Xn)

Energy(Xi) = min(|X(i-1) - Xi|, |X(i+1) - Xi|), 1 < i <n

j <- 1
while j < n - k do
    X.Exclude(min(Energy(Xi)), 1 < i < n)
    j <- j + 1
    n <- n - 1
end while
于 2012-09-05T11:43:55.817 に答える
0

O(n*(log n) + n*log(M))でこれを行うことができMますmax(A) - min(A)。

アイデアは、二分探索を使用して、可能な最大の分離を見つけることです。

まず、配列をソートします。d次に、距離 を受け取り、少なくとも で区切られた連続する要素で可能な限り最長の部分配列を貪欲に構築するヘルパー関数が必要dです。時間内にこれを行うことができますO(n)。

生成された配列の長さが少なくともkである場合、可能な最大の分離は>=dです。それ以外の場合は、厳密に 未満ですd。これは、二分探索を使用して最大値を見つけることができることを意味します。ある程度の賢さで、二分探索の「下限」と「上限」を縮小できますが、すでに非常に高速であるため、並べ替えがボトルネックになります。

Python コード:

def maximize_distance(nums: List[int], k: int) -> List[int]:
    """Given an array of numbers and size k, uses binary search
    to find a subset of size k with maximum min-pairwise-distance"""
    assert len(nums) >= k
    
    if k == 1:
        return [nums[0]]

    nums.sort()

    def longest_separated_array(desired_distance: int) -> List[int]:
        """Given a distance, returns a subarray of nums
        of length k with pairwise differences at least that distance (if
        one exists)."""

        answer = [nums[0]]

        for x in nums[1:]:

            if x - answer[-1] >= desired_distance:
                answer.append(x)

                if len(answer) == k:
                    break

        return answer

    low, high = 0, (nums[-1] - nums[0])

    while low < high:
        mid = (low + high + 1) // 2

        if len(longest_separated_array(mid)) == k:
            low = mid
        else:
            high = mid - 1

    return longest_separated_array(low)
于 2022-02-06T06:54:24.910 に答える