采访 - 在数组中查找幅度极

问题描述

幅度极：在一个数组，其左手侧元件都小于或等于它而其右手侧元件都大于或等于它的元素

例如输入

  3,1,4,5,9,7,6,11
 

所需的输出

  5,11
 

有人问我，在接受记者采访这个问题，我要返回元素的索引，只返回满足条件的第一个元素。

我的逻辑

code

  INT magnitudePole（常量矢量＆lt; INT＆GT;＆安培; A）{
   多集＆LT; INT＆GT;左右;
   INT left_max，right_min;
   INT大小= A.size（）;
   的for（int i = 1; I＆LT;大小; ++ I）
       right.insert（A [1]）;
   right_min = *（right.begin（））;
   若（a [0]＆LT; = right_min）
       返回0;
   left.insert（A [0]）;
   的for（int i = 1; I＆LT;大小; ++ I）{
       right.erase（right.find（A [1]））;
       left_max = *（ -  left.end（））;
       如果（right.size（）大于0）
           right_min = *（right.begin（））;
       如果（A [I]＆GT; left_max和放大器;＆放大器; A [1]  -  = right_min）
           返回我;
       其他
           left.insert（A [1]）;
   }
   返回-1;
}
 

我的提问

解决方案

对于一个O（n）的算法：

1. 计数在[0从n个[0]对于所有的k的最大元素到n [k]的，长度（n））的，保存在一个数组maxOnTheLeft答案。此费用为O（n）;
2. 计数从n个[k]的最小的元素到n [长度（正）-1]为在所有的k [0，长度（n））的，保存在一个数组minOnTheRight答案。此费用为O（n）;
3. 遍历整个事情，并找到maxOnTheLeft＆LT任意n [K] = N [K]＆LT; = minOnTheRight。此费用为O（n）。

和你code是（至少）错在这里：

 如果（A [I]＆GT; left_max和放大器;＆放大器; A [1]  -  = right_min）//＆LT;  - 应该是＆GT; =和＆lt; =
 

Magnitude Pole: An element in an array whose left hand side elements are lesser than or equal to it and whose right hand side element are greater than or equal to it.

example input

3,1,4,5,9,7,6,11

desired output

5,11

I was asked this question in an interview and I have to return the index of the element and only return the first element that met the condition.

My logic

Code

int magnitudePole (const vector<int> &A) {
   multiset<int> left, right;
   int left_max, right_min;
   int size = A.size();
   for (int i = 1; i < size; ++i)
       right.insert(A[i]);
   right_min = *(right.begin());
   if(A[0] <= right_min)
       return 0;
   left.insert(A[0]);
   for (int i = 1; i < size; ++i) {
       right.erase(right.find(A[i]));
       left_max = *(--left.end());
       if (right.size() > 0)
           right_min = *(right.begin());
       if (A[i] > left_max && A[i] <= right_min)
           return i;
       else
           left.insert(A[i]);
   }
   return -1;
}

My questions

解决方案

For an O(n) algorithm:

1. Count the largest element from n[0] to n[k] for all k in [0, length(n)), save the answer in an array maxOnTheLeft. This costs O(n);
2. Count the smallest element from n[k] to n[length(n)-1] for all k in [0, length(n)), save the answer in an array minOnTheRight. This costs O(n);
3. Loop through the whole thing and find any n[k] with maxOnTheLeft <= n[k] <= minOnTheRight. This costs O(n).

And you code is (at least) wrong here:

if (A[i] > left_max && A[i] <= right_min) // <-- should be >= and <=

这篇关于采访 - 在数组中查找幅度极的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！