如何以递增的顺序找到3个数字并在线性时间内增加数组中的索引

Question

我在一个网站上遇到过这个问题.正如那里提到的那样,在亚马逊的采访中被问到了.在给定的约束条件下,我无法找到合适的解决方案.

给定一个n整数数组,找到3个元素,a[i] < a[j] < a[k]并i < j < k在O(n)时间内.

Answer 1

所以这是你如何解决问题.您需要迭代数组三次.在第一次迭代时,标记右侧和第二次迭代中具有大于它们的元素的所有值,标记左侧小于它们的所有元素.现在你的回答是一个包含两个元素的元素:

int greater_on_right[SIZE];
int smaller_on_left[SIZE];
memset(greater_on_rigth, -1, sizeof(greater_on_right));
memset(smaller_on_left, -1, sizeof(greater_on_right));

int n; // number of elements;
int a[n]; // actual elements;
int greatest_value_so_far = a[n- 1];
int greatest_index = n- 1;
for (int i = n -2; i >= 0; --i) {
   if (greatest_value_so_far > a[i]) {
     greater_on_right[i] = greatest_index;
   } else {
     greatest_value_so_far = a[i];
     greatest_index = i;
   }
}

// Do the same on the left with smaller values


for (int i =0;i<n;++i) {
  if (greater_on_right[i] != -1 && smaller_on_left[i] != -1) {
    cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_right[i] << endl;
  }
}

该解决方案在整个阵列上迭代3次,因此是线性的.我没有提供整个解决方案,所以你可以在左边训练自己,看看你是否明白我的想法.我很抱歉不提供一些提示,但我无法弄清楚如何在没有显示实际解决方案的情况下给出提示.

希望这能解决你的问题.