9

重複を含む可能性のある配列が与えられた場合、それがシーケンスであるかどうかをどのように確認できますか?

例えば。{7, 3, 5, 4, 6, 2}

シーケンスです2, 3, 4, 5, 6, 7

並べ替えは明らかな解決策です。O(n) 時間と O(1) 空間でこれを行うにはどうすればよいでしょうか?

4

3 に答える 3

10

1,2,3,3,4,1が有効なソートされていないシーケンスで2,4,6,8あり、(ステップ 2 の) 有効なシーケンスでもあると仮定しますが、そう1,3,5,9ではなく (7 がありません)、入力配列を上書きできると仮定します。

  1. 最大値と最小値を決定します: O(n) 時間、O(1) スペース。これには、配列の最初と最後の位置を使用できます。
  2. ステップを決定します。ステップは、すべての乗数の中で最も一般的でない乗数ですa_n - min
  3. それらが離れすぎている場合 ( max - min > (count + 1) * step)、これはシーケンスではありません。さもないと、
  4. インプレース整数ソートを行います。開始 > 終了まで:
    • 最初の位置を見てください。そこに値を入れましょうv_0
    • 重複がないと仮定したときの目標位置 ( (v_0 - min) / step + start) をi
      • ターゲットの掲載順位が 未満startの場合、重複しています。後ろに移動し、エンドポインターをデクリメントします
      • ターゲットの位置が より大きい場合end、シーケンス内に欠落している要素があります。配列がシーケンスではないと主張します。
    • 要素がターゲット位置にある場合は、開始ポインターとmin参照をインクリメントします
    • それ以外の場合、ターゲット位置の要素が参照の最小値より小さいか等しい場合はv_0、それを配列の最後にスワップし、終了ポインターをデクリメントします。複製です。
    • それ以外の場合は、ターゲット位置の要素を でスワップしv_0ます。
  5. 配列にシーケンスを要求する

インプレース整数ソートは O(n) です。各ステップで、次のいずれかです。

  • 入力配列を短縮し、ソートされたすべての要素をターゲット位置に保持するか、
  • 1 つまたは 2 つの以前に並べ替えられていない要素を目的の位置に並べ替えます。

並べ替えの最後に、各要素は重複ブロック内で重複しているか、並べ替えられたブロック内の正しい位置にあります。

手順 3 は省略できることに注意してください。＃4は、これがシーケンスではないと正しく判断しますが、遅くなります。

ステップが 1 でなければならない場合、このアルゴリズムはいくらか単純化できます (リビジョン #1 を参照)。

于 2013-08-07T11:42:01.247 に答える
1

このアルゴリズム (Python) は元の配列を破棄しますが、それ以外の場合は O(n) 時間と O(1) 余分なスペースを満たします。

# INPUT: An array 'arr' of N integers.
# OUTPUT: If the array consists exactly of the integers
#         S, S+1, ..., S+N-1, for some S, in any order,
#         then modifies 'arr' into a sorted array and returns it.
#         Otherwise, returns False, and 'arr' may have been modified.
def sort_sequence (arr):
    the_min = min(arr)
    the_max = max(arr)
    if the_max - the_min != len(arr) - 1:
        return False
    for i in range(len(arr)):
        arr[i] -= the_min
    for i in range(len(arr)):
        while arr[i] != i:
            j = arr[i]
            t = arr[j]
            if t == j:
                return False
            arr[j] = j
            arr[i] = t
    for i in range(len(arr)):
        arr[i] += the_min
    return arr

まだ機能することを正式に証明していません。

これはなぜ O(n) なのですか? 最後の二重ループでは、要素が最初に正しい場所に配置された後、もう一度だけアクセスできます - 正しい場所にあると見なされる別の内部ループの開始時、または見つかった場所のいずれかです。重複する要素 (if t == hパーツ) の邪魔にならないようにします。

于 2013-08-07T12:21:21.250 に答える
-1

試してみましょう：

  1. 最小値と最大値を決定 – O(n)
  2. 元の配列のサイズの null 許容値の配列を作成します – O(n) (はい、ここにスペース要件がありません)
  3. 元の配列 (O(n)) を反復処理し、見つかった数値をインデックス (数値 - 分) に配置します。そこに値が見つかった場合、シーケンスはありません。最後に来て位置がなかった場合主張した、あなたはシーケンスを持っています
public bool IsSequence(int[] values)
{
    var min = values[0];
    var max = values[0];
    foreach (var value in values)
    {
        min = min > value ? value : min;
        max = max > value ? max : value;
    }

    if ((max - min + 1) != values.Length)
        return false;

    var testingArray = new int?[values.Length];
    foreach (var value in values)
    {
        var index = value - min;
        if (testingArray[index].HasValue)
            return false;
        else
            testingArray[index] = value;
    }
    return true;
}
于 2013-08-07T11:31:57.883 に答える