如何确定一个序列是否是比特的？

Question

如果序列单调增加然后单调减少,或者如果它可以循环移位到单调增加然后单调减少,则序列是比特的.例如,序列(1,4,6,8,3,-2),(9,2,-4,-10,-5)和(1,2,3,4)是比特的,但是(1 ,3,12,4,2,10)不是苦味的.

如何确定给定的序列是否是比特的？

我有以下意见.我们可以走到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你的阵列是bitonic的话.
• 这个的运行时应该是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:它可以简化代码循环循环length + 1元素,这将保证你找到两个拐点.

注3:或者,如果你总是寻找增加到减少的第一个拐点(在搜索其他拐点之前),它可能会简化代码.这样,你的扫描只需要担心找到另一个相反翻转的另一个拐点.

注4:至于你的例子,你不能使用N/2,因为拐点不一定发生在数组的中点.