如何判断一个序列是否是双音序列？
如果一个序列单调增加然后单调减少，或者如果它可以循环到单调增加然后单调减少，那么它是双调的。例如，序列(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)])这是正确的吗？
回答 5
Stack Overflow用户
发布于 2010-06-13 01:40:43
双音序列：
/\
/ \
\/不是双音序列：
/\
/ \ / (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;
}Stack Overflow用户
发布于 2010-06-12 23:19:20
- 向前遍历数组，在到达末尾时回绕(代码如下)
- 计算您找到的拐点总数，如果为
num_inflection_points==2，则数组为二进制。 - 此函数的运行时应为
-
下面是一个用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;
}取决于您的implementation:的
- 备注
注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，因为拐点不一定出现在数组的中点。
Stack Overflow用户
发布于 2012-10-31 06:28:01
下面是一个高效而简单的Java实现。它只遍历数组一次，以确定该数组是否为bitonic。它使用一个变量reversal来计算数组中单调性的方向反转次数(包括循环回绕)。
变量trend可以有三个值：
如果值是same;
1，，则为0，；如果数组是单调递减的，则为increasing;-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;
}https://stackoverflow.com/questions/3029024
复制相似问题