1

配列と数値 N があります。

配列には、0、1、2、3....N の数値を入力できます。

たとえば、arr={1,0,2,3,1,0,2,4,3,1,0,2,4,3,0,0,0} //N=4の場合

すべての数字 1、2、...N を含む最小長のサブ配列を見つける必要があります。

たとえば、上記の配列の答えは {1,0,2,3,1,0, 2,4,3,1 ,0,2,4,3,0,0,0}// length=4である必要があります、インデックスは start=6、end=9、//0 ベース

上記の質問の可能な答えの 1 つは {1,0,2, 3,1,0,2,4 ,3,1,0,2,4,3,0,0,0} ですが、その長さは 5 であるため、拒否されました..最小の長さのサブ配列が複数ある場合、答えは1回出現するはずです。または、配列に 1、2、..N の間の 1 つまたは複数の数値が含まれていない場合、答えは「サブ配列が見つかりません」です。

これは私のpythonコードです.いくつかのケースでは間違った答えを出しています(私にはわかりません)...誰かが私が間違っていることを教えてくれたら.

shortlen=2000001 //initialise to INFINITY
shortstart=0 
matchln=len(match) //match is the array containing integers

while(i<matchln):
   if(match[i]>0):
    leng=0
    pos=[0]*n // array to keep status of found integers
    j=i
    start=i
    sums=0
    while(j<matchln and sums!=n):
        if(match[j]>0):
            if(pos[match[j]-1]==0): //only update status if the integer is not marked previously.
                pos.pop(match[j]-1)
                pos.insert(match[j]-1,1) //(match[j]-1) becuz array indexing is from 0.
                sums+=1


        j+=1

    leng=j-i

    if(j==matchln and sums!=n): // if the loop terminated,without marking all integers,that means we shouldn't proceed.
        break

    if(leng<shortlen): //if the length calculated is smaller then existing,then update it.
        shortlen=leng
        shortstart=start

i+=1
4

3 に答える 3

1

1 つの可能性は、各開始位置からの最短の長さを追跡することです。これを行うには、配列に対して 2 つのパスを実行します。

インデックス 1..k の場合、位置の後に見つかった一連の数値 (1..N 内) を維持していると仮定すると (位置ごとに異なるセット)、位置 k+1 に進むと、すべてのセットを更新する必要があります(* ) 位置 k+1 の番号 (番号が 1..N の範囲内である限り)。セットに N 個の要素が含まれたら、その開始位置の最短シーケンスを見つけ、その位置の長さを記録します。

(*) フルセットを持つ位置については、それらを反復する必要がなくなることに注意してください。また、ポジションのセットがいっぱいになると、その前のポジションのセットもいっぱいになる必要があるため、セットを確認するためにスライドする「開始位置」を保持できます

これで、別のパスを実行して、各位置で記録された最短のシーケンスを選択できるようになりました (開始位置とシーケンスの長さに基づいて終了位置を計算できます)。

status = new array[arr.length] of Status // for score keeping
// initialize Status with: set <- empty, length <- n+1
startPos = 1 // sliding start position
// first pass
for i = 1..arr.length
  if arr[i] > 0 // within 1..N
    for j = startPos..i
      status[j].set.add(arr[i])
      if status[j].set.size == N // we have all numbers
        status[j].length = i-j;
         startPos = j+1

min = n+1 // for the shortest length
startPos = 1
// second pass
for i = 1..status.length
  if status[i].length < min
    min = status[i].length
    startPos = i

if min < n+1
  // found a winner
  print("start: " + startPos + ", end: " + startPos + min)

注: 上記のコードのインデックスは (0 ではなく) 1 から始まります

于 2012-06-22T14:15:23.543 に答える
0

追加のハッシュテーブルが許可されている場合は、1回のパスで実行できます。

基本的に、配列上に2つのポインター（左と右）を維持します。どちらも最初は配列の最初の要素を指します。

各ラウンドでは、最初に右に進みます。最初の移動の後、右が左と同じ値を指すときはいつでも、左前方にも移動します。もちろん、0はスキップします。

各ラウンド中に、ハッシュテーブルを維持して、1からNまでのどの値が間隔[左、右]内にあるかを確認し、すべての値が間隔内にある場合は、間隔の長さを取得します。プロセス全体で最小間隔の長さを追跡します。

時間計算量はO（Nn）になります

于 2012-06-22T20:07:11.620 に答える
0

それはあなたを助けるかもしれないと思います。問題の目標は、値を線形独立シーケンスに変換することです。私はあなたの問題を解決するために小さなコードを書きました.それはあなたが望むシーケンスの始まりを見つけます:

#include <stdio.h>
void main(){
/*By Volnei Klehm,
 Manaus-AM, Brazil
    2012
*/
long long arr[]={1,0,2,3,1,0,2,4,3,1,0,2,4,3,0,0,0};
long long power2arr[17]; /*same size or larger than arr*/
long long powerSum=0;
long long partialSum=0;
int count,count1,N;

int size_arr;
size_arr=sizeof(arr)/sizeof(long long);

/*the goal here is to find a way to represent your values as linear indepent ones,
      here a sequece of power of 2 is used, you can also use other ways to do it that not increases so dramatically in values.
      I use powers of 2 cause is more easy handled by computers, you can also use a sequence of sines, 
      cosines or any other math way that produces independets values. 
      For more informations I suggest you to take a look in linear algebra and/or digital signal processing books*/


/*Now it computes an independent basis*/

for(count=0 ; count<size_arr ; ++count){
    power2arr[count] = 1 << arr[count]; /*calculates 2^arr generating a set of independent numbers.*/

}

N=4; /*put here your N, for n=4 it will look for*/
/*Notice that deppending on your system, N cannot be too large,
      at certain point N values can make 2^N too large to be handled 
      by standard c/c++ types. Here is safe to use n up to 63.*/

/*now it gets the sum results of 2^0 + 2^1 + 2^2 ... + 2^N*/

++N; /* in C position starts at 0*/

for(count = 0 ; count < N ; count++)
    powerSum |= 1 << count;

for(count = 0 ; count<size_arr ; ++count){
    partialSum=0;
    for(count1 = count ; count1 < (count + N) ; count1++){
        if((count + N) > size_arr){
            printf("No occurrences found!\n");
            return;
        }
        partialSum |= power2arr[count1];    
    }
    if(partialSum==powerSum){
        printf("Ocurrence found at: %d\n", count);
        return;
    }
}

}

于 2012-06-22T19:02:45.883 に答える