采访 - 在数组中查找幅度极 [英] Interview - Find magnitude pole in an array

问题描述

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

例如输入

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

所需的输出

  5,11
 

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

我的逻辑

  

  
1. 举两个多集（这样我们就可以考虑复制以及），一个用于元素的右侧，一个用于左侧   元素（杆）。
  
2. 在开始用0号元素，并把其余全部元素正确设置。
  
3. 如果这第0个元素是小于等于对正确设置，然后返回其索引的所有元素基本条件。
  
4. 否则将其放入左集，并开始与元素索引1
  
5. 遍历数组，每一次选择从左集和右设定最小值最大值和比较。
  
6. 在的时候对任何元素的所有价值，它的左边是左集和价值，其右侧任意时刻都在正确设置
  

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）时间。
  

解决方案

对于一个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

1. Take two MultiSet (So that we can consider duplicate as well), one for right hand side of the element and one for left hand side of the element(the pole).
2. Start with 0th element and put rest all elements in the "right set".
3. Base condition if this 0th element is lesser or equal to all element on "right set" then return its index.
4. Else put this into "left set" and start with element at index 1.
5. Traverse the Array and each time pick the maximum value from "left set" and minimum value from "right set" and compare.
6. At any instant of time for any element all the value to its left are in the "left set" and value to its right are in the "right set"

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

• I was told that my logic is incorrect, I am not able to understand why this logic is incorrect (though I have checked for some cases and it is returning right index)
• For my own curiosity how to do this without using any set/multiset in O(n) time.

解决方案

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 <=

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