如何确定序列是否为双音？ [英] How to determine if a sequence is bitonic?

问题描述

如果序列单调增加然后单调减少
折痕，或者可以循环移位为单调增加然后
单调减少，则该序列是双音调的。例如序列（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]）和（a [n-i-1]< a [n-1-（i + 1）]）
  

这正确吗？

解决方案

一个音调序列：

  / \ 
 / \ 
 \ / 
  

非双音序列：

  / \ 
 / \ /（高于开始位置）
 \ / 
  

很明显，如果方向变化两次以上，我们就不会有一个音调序列。

如果方向变化小于两次，我们就必须有一个音调序列。 / p>

如果方向发生两个变化，我们可以有一个双音序列。考虑上面的两个ascii图像。显然，具有两个方向变化的序列将匹配其中一种模式（允许反射）。因此，我们通过比较第一个和最后一个元素来设置初始方向。由于这些可以相同，因此我们使用不等于最后一个元素的第一个元素。

这是Java中的实现：

  public static Boolean bitonic（int [] array）{
 if（array == null）返回false; 
 if（array.length< 4）返回true; 
布尔值dir; // false减小，true增大
 int pos = 0，开关= 0; 
而（pos< array.length）{
 if（array [pos]！= array [array.length-1]）$ ​​b $ b休息； 
 pos ++; 
} 
如果（pos == array.length）返回true; 
 // pos这是第一个与最后一个
不同的元素dir = array [pos]> array [array.length-1]; 
而（pos< array.length-1&&开关< = 2）{
 if（（array [pos + 1]！= array [pos]）&&
（（array [pos + 1]< = array [pos]）== dir））{
 dir ^ = true; 
开关++; 
} 
 pos ++; 
} 
返回开关< = 2; 
} 
  

A sequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. For example the sequences (1, 4, 6, 8, 3, −2) , (9, 2, −4, −10, −5) , and (1, 2, 3, 4) are bitonic, but (1, 3, 12, 4, 2, 10) is not bitonic.

How can it be determined if given sequence is bitonic?

I have the following opinion. We can walk till n/2, where n is the length of the array, and check if

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

Is this correct?

解决方案

A bitonic sequence:

 /\
/  \
    \/

Not a bitonic sequence:

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

Obviously if the direction changes more than two times we cannot have a bitonic sequence.
If the direction changes less than two times, we must have a bitonic sequence.

If there are two changes in direction, we MAY have a bitonic sequence. Consider the two ascii images above. Clearly a sequence with two changes in direction will match one of the patterns (allowing for a reflection). Thus, we set the initial direction by comparing the first and last elements. Since these can be the same, we use the first element that is not equal to the last element.

Here is an implementation in 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;
}

这篇关于如何确定序列是否为双音？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！