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

Question

Последовательность битонна, если она монотонно увеличивается, а затем монотонно складки, или если это может быть смещено по кругу, чтобы монотонно увеличиваться, а затем монотонно уменьшается. Например, последовательности (1, 4, 6, 8, 3, -2), (9, 2, −4, −10, −5) и (1, 2, 3, 4) являются битовыми, но (1, 3, 12, 4, 2, 10) bitonic.

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

У меня есть следующее мнение. Мы можем идти до n / 2 , где n - длина массива, и проверить, если

(a[i] < a[i + 1]) and (a[n - i - 1] < a[n-1 - (i + 1)])

Это правильно?

Answer 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;
}

Answer 2

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

-

Вот рабочий пример на c ++:

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. Это может упростить код для циклического цикла * 1023.* elemnts, который гарантирует, что вы найдете обе точки перегиба.

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

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

Answer 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;
}

Answer 4

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

Answer 5

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

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

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