4

ソート済みstd::vector<int>で、このベクトルで最長の「連続する数値のストリーク」を見つけて、その長さとストリーク内の最小の数値の両方を返したいと思います。

あなたのためにそれを視覚化するために：私たちが持っていると仮定します： 1 3 4 5 6 8 9

私はそれを返したいです：maxStreakLength = 4そしてstreakBase = 3

2本の筋があり、どちらが長いかを選択しなければならない場合があります。

これを行うための最良の（最速の）方法は何ですか？これを実装しようとしましたが、ベクトル内の複数のストリークに対処するのに問題があります。一時的なベクトルを使用して、それらの長さを比較する必要がありますか？

4

5 に答える 5

7

いいえ、これをベクトルの1回のパスで実行し、これまでに見つかった最長の開始点と長さのみを保存することはできません。また、必要な比較は「N」よりはるかに少なくなります。*

ヒント：5番目の位置（= 6）で終わる4つの長い試合をすでに言っている場合、次にどの位置を確認する必要がありますか？

[*] O（）の複雑さの可能性を理解するための演習として読者に任せました;-)

于 2012-07-25T15:06:46.193 に答える
3

配列がソートされているという事実を利用して、アルゴリズムを改善できるかどうかを確認するのは興味深いことです。最初に頭に浮かぶのは、これです。入力配列内のすべての数値が一意であることがわかっている場合、配列内の要素の範囲について[i, j]、実際に調べなくても、その範囲内の要素が連続しているかどうかをすぐに判断できます。範囲を介して。この関係が成り立つ場合

array[j] - array[i]  ==  j - i

そうすれば、その範囲の要素は連続しているとすぐに言うことができます。この基準は、明らかに、配列がソートされており、数値が繰り返されないという事実を使用しています。

ここで、その基準を利用するアルゴリズムを開発する必要があります。考えられる再帰的アプローチの1つは次のとおりです。

  1. 再帰ステップの入力は要素の範囲です[i, j]。最初は[0, n-1]、配列全体です。
  2. 上記の基準を範囲に適用します[i, j]。範囲が連続していることが判明した場合、それをさらに細分化する必要はありません。範囲を出力に送信します（詳細については、以下を参照してください）。
  3. [i, m]それ以外の場合（範囲が連続していない場合）、2つの等しい部分とに分割し[m+1, j]ます。
  4. 下部（[i, m]）でアルゴリズムを再帰的に呼び出し、次に上部（）でアルゴリズムを呼び出し[m+1, j]ます。

上記のアルゴリズムは、左から最初のアプローチを使用して、配列のバイナリパーティションとパーティションツリーの再帰下降を実行します。これは、このアルゴリズムが左から右の順序で連続する要素を持つ隣接するサブ範囲を見つけることを意味します。あなたがする必要があるのは、隣接するサブレンジを一緒に結合することです。手順2で「出力に送信」されたサブ範囲を受信した[i, j]場合、それらが実際に連続している場合は、以前に受信したサブ範囲と連結する必要があります。または、連続していない場合は、新しい範囲を開始する必要があります。その間ずっと、これまでに見つかった「最長の連続範囲」を追跡しています。

それでおしまい。

このアルゴリズムの利点は、連続する要素のサブレンジを、これらのサブレンジの内部を見ることなく「早期に」検出することです。明らかに、最悪の場合のパフォーマンス（連続するサブ範囲がまったくない場合）はまだO(n)です。最良の場合、入力配列全体が連続している場合、このアルゴリズムはそれを即座に検出します。（私はまだこのアルゴリズムの意味のあるO推定に取り組んでいます。）

このアルゴリズムの使いやすさは、一意性の要件によって損なわれます。あなたの場合、それが「与えられた」ものであるかどうかはわかりません。

とにかく、これが可能なC++実装です

typedef std::vector<int> vint;
typedef std::pair<vint::size_type, vint::size_type> range;

class longest_sequence
{
public:
  const range& operator ()(const vint &v)
  { 
    current = max = range(0, 0);

    process_subrange(v, 0, v.size() - 1);
    check_record();

    return max;
  }

private:
  range current, max;

  void process_subrange(const vint &v, vint::size_type i, vint::size_type j);
  void check_record();
};

void longest_sequence::process_subrange(const vint &v, 
                                        vint::size_type i, vint::size_type j)
{
  assert(i <= j && v[i] <= v[j]);
  assert(i == 0 || i == current.second + 1);

  if (v[j] - v[i] == j - i)
  { // Consecutive subrange found
    assert(v[current.second] <= v[i]);
    if (i == 0 || v[i] == v[current.second] + 1)
      // Append to the current range
      current.second = j;
    else
    { // Range finished
      // Check against the record 
      check_record();
      // Start a new range
      current = range(i, j);
    }
  }
  else
  { // Subdivision and recursive calls
    assert(i < j);
    vint::size_type m = (i + j) / 2;
    process_subrange(v, i, m);
    process_subrange(v, m + 1, j);
  }
}

void longest_sequence::check_record()
{
  assert(current.second >= current.first);
  if (current.second - current.first > max.second - max.first)
    // We have a new record
    max = current;
}

int main()
{
  int a[] = { 1, 3, 4, 5, 6, 8, 9 };
  std::vector<int> v(a, a + sizeof a / sizeof *a);
  range r = longest_sequence()(v);
  return 0;
}
于 2012-07-25T16:54:28.690 に答える
1

私はこれがそれをするべきだと信じていますか？

size_t beginStreak = 0;
size_t streakLen = 1;
size_t longest = 0;
size_t longestStart = 0;
for (size_t i=1; i < len.size(); i++) {
    if (vec[i] == vec[i-1] + 1) {
        streakLen++;
    }
    else {
        if (streakLen > longest) {
            longest = streakLen;
            longestStart = beginStreak;
        }
        beginStreak = i;
        streakLen = 1;
    }
}
if (streakLen > longest) {
    longest = streakLen;
    longestStart = beginStreak;
}
于 2012-07-25T15:06:58.347 に答える
1

この問題を短時間で解決することはできませんO(N)。N-1リストが最初の偶数と1つの奇数（最初のN-1奇数から選択）であると想像してください。次に、リストのどこかに長さ3の単一のストリークがありますが、最悪の場合、リスト全体をスキャンして見つける必要があります。平均でも、リストの少なくとも半分を調べて見つける必要があります。

于 2012-07-26T05:11:44.673 に答える
0

Rodrigoのソリューションに似ていますが、例も解決します。

#include <vector>
#include <cstdio>

#define len(x) sizeof(x) / sizeof(x[0])

using namespace std;

int nums[] = {1,3,4,5,6,8,9};
int streakBase = nums[0];
int maxStreakLength = 1;

void updateStreak(int currentStreakLength, int currentStreakBase) {
  if (currentStreakLength > maxStreakLength) {
    maxStreakLength = currentStreakLength;
    streakBase = currentStreakBase;
  }
}

int main(void) {
  vector<int> v;
  for(size_t i=0; i < len(nums); ++i)
    v.push_back(nums[i]);

  int lastBase = v[0], currentStreakBase = v[0], currentStreakLength = 1;

  for(size_t i=1; i < v.size(); ++i) {
    if (v[i] == lastBase + 1) {
      currentStreakLength++;
      lastBase = v[i];
    } else {
      updateStreak(currentStreakLength, currentStreakBase);
      currentStreakBase = v[i];
      lastBase = v[i];
      currentStreakLength = 1;
    }
  }
  updateStreak(currentStreakLength, currentStreakBase);
  printf("maxStreakLength = %d and streakBase = %d\n", maxStreakLength, streakBase);

  return 0;
}
于 2012-07-25T15:36:32.267 に答える