16

整数の配列が与えられます。範囲内のすべての数値が配列に存在するように、最大​​範囲を出力する必要があります。番号は任意の順序で存在する可能性があります。たとえば、配列が

{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15}

ここでは、これらの範囲内のすべての整数が配列に存在する 2 つの (自明ではない) 範囲、つまり [2,8] と [10,12] を見つけます。これらのうち [2,8] は長い方です。したがって、それを出力する必要があります。

この質問をされたとき、並べ替えを使用せずに線形時間でこれを行うように求められました。ハッシュベースの解決策があるのではないかと考えましたが、何も思いつきませんでした。

これが私の解決策の試みです：

void printRange(int arr[])
{
    int n=sizeof(arr)/sizeof(int);
    int size=2;
    int tempans[2]; 

    int answer[2];// the range is stored in another array
    for(int i =0;i<n;i++)
    {
        if(arr[0]<arr[1])
        {
             answer[0]=arr[0];
             answer[1]=arr[1];
        }
        if(arr[1]<arr[0])
        {
            answer[0]=arr[1];
            answer[1]=arr[0];
        }

        if(arr[i] < answer[1])
            size += 1;
        else if(arr[i]>answer[1]) {
            initialize tempans to new range;
             size2=2;
        }
        else { 
            initialize tempans  to new range
        }
}

//I have to check when the count becomes equal to the diff of the range

この部分で立ち往生しています...いくつの tempanswer[] 配列を使用する必要があるかわかりません。

4

9 に答える 9

10

次の解決策は、O(n) 空間を使用して O(n) 時間で機能すると思います。

配列内のすべてのエントリをハッシュ テーブルに入れることから始めます。次に、「訪問」した要素を格納する 2 番目のハッシュ テーブルを作成します。これは最初は空です。

次に、要素の配列を一度に 1 つずつ繰り返します。各要素について、要素が訪問済みセットにあるかどうかを確認します。その場合は、スキップしてください。それ以外の場合は、その要素から上に数えます。各ステップで、現在の番号がメイン ハッシュ テーブルにあるかどうかを確認します。その場合は、先に進み、現在の値を訪問済みセットの一部としてマークします。そうでない場合は、停止します。次に、下に数えることを除いて、この手順を繰り返します。これにより、この特定の配列値を含む範囲内の連続する要素の数がわかります。この方法で見つかった最大範囲を追跡すると、問題の解決策が得られます。

このアルゴリズムの実行時の複雑さは O(n) です。これを確認するには、最初のステップで O(n) 時間でハッシュ テーブルを作成できることに注意してください。次に、最大範囲を見つけるために配列のスキャンを開始すると、スキャンされる各範囲には、その範囲の長さに比例して時間がかかります。範囲の長さの合計は元の配列の要素の数であり、同じ範囲を 2 回スキャンすることはないため (訪問する各数値をマークするため)、この 2 番目のステップには O(n) 時間がかかります。まあ、O（n）の正味実行時間の場合。

編集:興味がある場合は、このアルゴリズムのJava 実装と、それが機能する理由と正しいランタイムを持つ理由のより詳細な分析があります。また、アルゴリズムの最初の説明では明らかでないいくつかのエッジ ケース (たとえば、整数オーバーフローの処理方法) についても説明します。

お役に立てれば！

于 2011-03-24T06:25:12.167 に答える
8

ソリューションは次を使用できますBitSet：

public static void detect(int []ns) {
    BitSet bs = new BitSet();
    for (int i = 0; i < ns.length; i++) {
        bs.set(ns[i]);
    }
    int begin = 0;
    int setpos = -1;
    while((setpos = bs.nextSetBit(begin)) >= 0) {
        begin = bs.nextClearBit(setpos);
        System.out.print("[" + setpos + " , " + (begin - 1) + "]");
    }
}

サンプル I/O: 

detect(new int[] {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15} );
[2,8] [10,12] [15,15]
于 2011-03-24T13:24:05.433 に答える
0

実際には、整数のみをソートしているため、比較ソートは必要ないことを考慮すると、Radix- または BucketSort を使用して配列をソートし、それを反復処理することができます。

シンプルで、確かにインタビュー対象者が聞きたかったことではありませんが、それでも正しいです ;)

于 2011-03-24T15:43:24.003 に答える
0

Javascriptスパース配列機能を使用した非常に短いソリューション:

O(n) の追加スペースを使用して O(n) 時間。

var arr = [2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15];

var a = [];
var count = 0, max_count = 0;

for (var i=0; i < arr.length; i++) a[arr[i]] = true;
for (i = 0; i < a.length; i++) {
    count = (a[i]) ? count + 1 : 0;
    max_count = Math.max(max_count, count);
    }

console.log(max_count); // 7
于 2020-06-06T21:57:52.577 に答える
0

この問題に対する複数のプラットフォームでの多くの解決策を読みましたが、問題を非常にエレガントに解決し、簡単に追跡できるため、注目を集めました。

このメソッドのバックボーンは、O(n) 時間かかるセット/ハッシュを作成することであり、そこからセット/ハッシュへのすべてのアクセスは O(1) になります。O 記法では定数項が省略されているため、このアルゴリズムは全体として次のように記述できます。 O(n)

def longestConsecutive(self, nums):
    nums = set(nums)                    # Create Hash O(1)   
    best = 0
    for x in nums:                   
        if x - 1 not in nums:           # Optimization
            y = x + 1                   # Get possible next number
            while y in nums:            # If the next number is in set/hash
                y += 1                  # keep counting
            best = max(best, y - x)     # counting done, update best
    return best

単純な数字でそれを実行した場合、それは簡単です。ステップは、そのOptimization特定の数がbeginningシーケンスの .

すべてのクレジットは Stefan Pochmann に帰属します。

于 2017-11-18T07:22:07.430 に答える
0

上記のテンプレートによる回答は機能しますが、ハッシュ テーブルは必要ありません。使用するアルゴリズムによっては、ハッシュに時間がかかる場合があります。インタビュアーに整数の最大数があるかどうか尋ねてから、そのサイズの配列を作成できます。それをexist[]と呼んでから、arrをスキャンしてexist[i] = 1;とマークします。次に、現在の最大範囲のサイズ、現在の最大範囲の開始点、現在の範囲のサイズ、および現在の範囲の開始点の 4 つの変数を追跡しながら、exist[] を反復処理します。exist[i] = 0 が表示されたら、現在の範囲値と最大範囲値を比較し、必要に応じて最大範囲値を更新します。

最大値がない場合は、ハッシュ方式を使用する必要がある場合があります。

于 2011-03-24T06:41:29.887 に答える
-1

それを行う簡単な方法（PHP）：

$tab = array(14,12,1,5,7,3,4,10,11,8);
asort($tab);
$tab = array_values($tab);
$tab_contiguous = array();
$i=0;
foreach ($tab as $key => $val) {
    $tab_contiguous[$i][] = $tab[$key];
    if (isset($tab[$key+1])) {
        if($tab[$key] + 1 != $tab[$key+1])
            $i++;
    }
}
echo(json_encode($tab_contiguous));
于 2015-11-18T16:37:12.217 に答える