Как определить, является ли последовательность битной?

Ответ 1

Битоновая последовательность:

 /\
/  \
    \/

Не битоническая последовательность:

 /\    
/  \  / (higher than start)
    \/

Очевидно, если направление меняется более двух раз, мы не можем иметь битоновую последовательность.
Если направление меняется менее двух раз, мы должны иметь битоновую последовательность.

Если есть два изменения направления, мы МОЖЕМ иметь битоновую последовательность. Рассмотрим два изображения ascii выше. Очевидно, что последовательность с двумя изменениями в направлении будет соответствовать одному из шаблонов (позволяющих отразить). Таким образом, мы устанавливаем начальное направление, сравнивая первый и последний элементы. Поскольку они могут быть одинаковыми, мы используем первый элемент, который не равен последнему элементу.

Вот реализация в Java:

public static Boolean bitonic(int[] array) {
    if (array == null) return false;
    if (array.length < 4) return true;
    Boolean dir;// false is decreasing, true is increasing
    int pos = 0, switches = 0;
    while (pos < array.length) {
        if (array[pos] != array[array.length - 1])
            break;
        pos++;
    }
    if (pos == array.length) return true;
    //pos here is the first element that differs from the last
    dir = array[pos] > array[array.length - 1];
    while (pos < array.length - 1 && switches <= 2) {
        if ((array[pos + 1] != array[pos]) &&
           ((array[pos + 1] <= array[pos]) == dir)) {
            dir ^= true;
            switches++;
        }
        pos++;
    }
    return switches <= 2;
}

Ответ 2

• Перемещение массива вперед, обертывание, когда вы попадаете в конец (код ниже)
• Подсчитайте общее количество точек перегиба, которые вы найдете, если num_inflection_points==2, то ваш массив будет битным.
• Время выполнения должно быть O(n).

-

Вот рабочий пример в С++:

bool is_bitonic(const vector<int>& v) {
  bool was_decreasing = v.back() > v.front();
  int num_inflections = 0;
  for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
    bool is_decreasing = v[i] > v[(i+1)%v.size()];
    // Check if this element and next one are an inflection.
    if (was_decreasing != is_decreasing) {
      num_inflections++;
      was_decreasing = is_decreasing;
    }
  }
  return 2 == num_inflections;
}

• Примечания, в зависимости от вашей реализации:

Примечание 1: Здесь основная идея для перемещения массива по кругу:

for (int i = ip_index; i < array_length; i++) {
   int index = (i + 1) % array_length;  // wraps around to beginning
   // Retrieve the value with
   DoSomethingWithValue(array[index];)
}

Примечание 2: Это может упростить код для циклического цикла length + 1 elemnts, что гарантирует, что вы найдете обе точки перегиба.

Примечание 3: Или это может упростить код, если вы всегда ищете первую точку перегиба, которая увеличивается до уменьшения (перед поиском других точек перегиба). Таким образом, ваше сканирование должно только беспокоиться о том, чтобы найти ровно одну другую точку перегиба с противоположным переворотом.

Примечание 4: Что касается вашего примера, вы не можете использовать N/2, потому что точка перегиба не обязательно встречается в середине массива.

Ответ 3

Вот эффективная и простая реализация на Java. Он обходит массив только один раз, чтобы определить, является ли массив битоником или нет. Он использует переменную reversal, которая подсчитывает количество обращений направления монотонности в массиве (включая круговую обертку вокруг).

Переменная trend может иметь три значения:

• 0, если значения одинаковы;
• 1, если массив монотонно возрастает,
• -1, если массив монотонно уменьшается.

public static boolean bitonic(int[] arr) {
  int reversal = 0;
  int len = arr.length;
  int trend = 0; // 0 means any, 1 means increasing, -1 means decreasing 
  for (int i= 0; i < len ; i++) {
    if(arr[i%len] < arr[(i+1)%len]){
      if (trend == 0) trend = 1;
      else if ( trend == -1) {
        reversal ++;
        trend = 1;
      }
    }
    else if(arr[i%len] > arr[(i+1)%len]){
      if (trend == 0) trend = -1;
      else if ( trend == 1) {
        reversal ++;
        trend = -1;
      }
    }
    if(reversal > 2) return false;
  }
  return true;
}

Ответ 4

Вы можете искать пик, т.е. когда [i-1] a [i] && a [i] > a [i + 1], тогда a [i] является локальным пиком (заботясь об обертке с помощью оператора модуля).

В биттонической последовательности может быть только один такой пик. Как только вы найдете пик, вы можете идти по склону влево (обертывая по мере необходимости, снова используя модуль), пока не найдете подъем. Затем вы вернетесь к вершине, идите вниз по склону, пока не найдете другую гору. Теперь, если последовательность биттонична, то вы охватите всю последовательность, спустившись вниз с обеих сторон.

Кстати, не понял ли я этот вопрос, или ваш первый пример не битничен?

Ответ 5

Там должно быть ровно два (или, в зависимости от того, как ваше определение имеет дело с вырождением, ровно 0) переходы между ростом и падением. Не забудьте проверить переход между [n] и [0].