如何找到在递增的顺序和线性时间在阵列中增加指数3号

问题描述

我碰到这个问题就来了一个网站。由于没有提到的，在亚马逊接受采访时被问。我无法弄清楚在给定的约束妥善解决。请帮助。

I came across this question on a website. As mentioned there, it was asked in amazon interview. I couldn't figure out a proper solution in given constraint. Please help.

由于n个整数数组，找出3个元素，使得[1] - ;一个研究[J] LT;一个[k]和I＆LT; J＆LT; K的0（n）时间。

Given an array of n integers, find 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time.

推荐答案

因此​​，这里是你如何解决这个问题。您需要遍历数组的两倍以上。在第一次迭代标记所有比他们更大的权利，并在第二次迭代标记的所有元素在其左侧的元素比他们更小的值。现在，你的答案会与既有的元素：

So here is how you can solve the problem. You need to iterate over the array twice. On the first iteration mark all the values that have an element greater than them on the right and on the second iteration mark all the elements smaller than them on their left. Now your answer would be with an element that has both:

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_rigth[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_rigth[i] != -1 && smaller_on_left[i] != -1) {
    cout << "Indices:" << smaller_on_left[i] << ", " << i << ", " << greater_on_rigth[i] << endl;
  }
}

此解决方案迭代3次通过整个数组，因此是线性的。我还没有提供的整体解决方案，让你可以训练自己在左边，看看你得到我的想法。不好意思不给只是一些技巧，但我无法弄清楚如何给小费，而不显示实际的解决方案。

This solution iterates 3 times over the whole array and is therefore linear. I have not provided the whole solution so that you can train yourself on the left to see if you get my idea. I am sorry not to give just some tips but I couldn't figure out how to give a tip without showing the actual solution.

希望这会解决您的问题。

Hope this solves your problem.

这篇关于如何找到在递增的顺序和线性时间在阵列中增加指数3号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！