algorithm - 面试 - 在数组中查找幅度极点

Question

Magnitude Pole：数组中的一个元素，其左侧元素小于或等于它，而右侧元素大于或等于它。

示例输入

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

期望的输出

4,5,11

我在一次采访中被问到这个问题，我必须返回元素的索引并且只返回满足条件的第一个元素。

我的逻辑

取两个 MultiSet（这样我们也可以考虑重复），一个用于元素的右侧，一个用于元素的左侧（极点）。

从第 0 个元素开始，将其余所有元素放在“正确的集合”中。

如果此第 0 个元素小于或等于“右集”上的所有元素，则基本条件，则返回其索引。

否则将其放入“左集”并从索引 1 处的元素开始。

遍历数组，每次从“左集”中选择最大值，从“右集”中选择最小值并进行比较。

在任何时刻，对于任何元素，其左侧的所有值都在“左集”中，而其右侧的值在“右集”中

代码

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;
}

我的问题

有人告诉我我的逻辑不正确，我无法理解为什么这个逻辑不正确（尽管我已经检查了某些情况并且它返回了正确的索引）

为了我自己的好奇心，如何在 O(n) 时间内不使用任何集合/多集合来做到这一点。

score 9 · Accepted Answer

对于 O(n) 算法：

计算 [0, length(n)) 中所有 k 从 n[0] 到 n[k] 的最大元素，将答案保存在数组 maxOnTheLeft 中。这花费 O(n);
计算 [0, length(n)) 中所有 k 从 n[k] 到 n[length(n)-1] 的最小元素，将答案保存在数组 minOnTheRight 中。这花费 O(n);
遍历整个事情并找到 maxOnTheLeft <= n[k] <= minOnTheRight 的任何 n[k]。这需要 O(n)。

你的代码（至少）在这里是错误的：

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

score 3 · Accepted Answer

Java实现：

Collection<Integer> magnitudes(int[] A) {
    int length = A.length;
    // what's the maximum number from the beginning of the array till the current position
    int[] maxes = new int[A.length];
    // what's the minimum number from the current position till the end of the array
    int[] mins = new int[A.length];

    // build mins
    int min = mins[length - 1] = A[length - 1];
    for (int i = length - 2; i >= 0; i--) {
        if (A[i] < min) {
            min = A[i];
        }
        mins[i] = min;
    }

    // build maxes
    int max = maxes[0] = A[0];
    for (int i = 1; i < length; i++) {
        if (A[i] > max) {
            max = A[i];
        }
        maxes[i] = max;
    }

    Collection<Integer> result = new ArrayList<>();
    // use them to find the magnitudes if any exists
    for (int i = 0; i < length; i++) {
        if (A[i] >= maxes[i] && A[i] <= mins[i]) {
            // return here if first one only is needed
            result.add(A[i]);
        }
    }
    return result;
}

score 3 · Accepted Answer

创建两个 bool[N] 称为 NorthPole 和 SouthPole（只是为了幽默。
通过 A[] 跟踪到目前为止找到的最大元素，如果 A[i] > Max(A[0..i-1]) 则将 SouthPole[i] 设置为 true
如果 A[i] < Min(A[i+1..N-1)，则通过 A[] 后退并设置 NorthPole[i] true
通过 NorthPole 和 SouthPole 向前走，找到都设置为 true 的第一个元素。

上面每一步都是O(N)，因为访问每个节点一次，所以总体上是O(N)。

score 1 · Accepted Answer

您的逻辑似乎完全正确（但没有检查实现）并且可以实现以提供 O(n) 时间算法！很好的工作思维在集合方面。

您的右集可以实现为支持最小值的堆栈，而左集可以实现为支持最大值的堆栈，这给出了 O(n) 时间算法。

拥有一个支持 max/min 的堆栈是一个众所周知的面试问题，并且每次操作都可以这样做（push/pop/min/max 为 O(1)）。

要将其用于您的逻辑，伪代码将如下所示

foreach elem in a[n-1 to 0]
    right_set.push(elem)

while (right_set.has_elements()) {
   candidate = right_set.pop();
   if (left_set.has_elements() && left_set.max() <= candidate <= right_set.min()) {
       break;
   } else if (!left.has_elements() && candidate <= right_set.min() {
        break;
   }
   left_set.push(candidate);
}

return candidate

score 1 · Accepted Answer

我在 Codility 上看到了这个问题，用 Perl 解决了这个问题：

sub solution {
        my (@A) = @_;            

        my ($max, $min) = ($A[0], $A[-1]);
        my %candidates;

        for my $i (0..$#A) {
                if ($A[$i] >= $max) {
                        $max = $A[$i];
                        $candidates{$i}++;
                }
        }
        for my $i (reverse 0..$#A) {
                if ($A[$i] <= $min) {
                        $min = $A[$i];
                        return $i if $candidates{$i};
                }
        }
        return -1;
}

score 0 · Accepted Answer

Create array of ints called mags, and int variable called maxMag.
For each element in source array check if element is greater or equal to maxMag.
If is: add element to mags array and set maxMag = element.
If isn't: loop through mags array and remove all elements lesser.

Result: array of magnitude poles

score 0 · Accepted Answer

有趣的问题，我在下面给出了自己的 C# 解决方案，请阅读评论以了解我的方法。

public int MagnitudePoleFinder(int[] A)
{
    //Create a variable to store Maximum Valued Item i.e. maxOfUp
    int maxOfUp = A[0];

    //if list has only one value return this value
    if (A.Length <= 1) return A[0];

    //create a collection for all candidates for magnitude pole that will be found in the iteration
    var magnitudeCandidates = new List<KeyValuePair<int, int>>();

    //add the first element as first candidate
    var a = A[0];
    magnitudeCandidates.Add(new KeyValuePair<int, int>(0, a));

    //lets iterate
    for (int i = 1; i < A.Length; i++)
    {
        a = A[i];
        //if this item is maximum or equal to all above items ( maxofUp will hold max value of all the above items)
        if (a >= maxOfUp)
        {
            //add it to candidate list
            magnitudeCandidates.Add(new KeyValuePair<int, int>(i, a));
            maxOfUp = a;
        }
        else
        {
            //remote all the candidates having greater values to this item
            magnitudeCandidates = magnitudeCandidates.Except(magnitudeCandidates.Where(c => c.Value > a)).ToList();
        }
    }
    //if no candidate return -1
    if (magnitudeCandidates.Count == 0) return -1;
    else
        //return value of first candidate
        return magnitudeCandidates.First().Key;
}

score 0 · Accepted Answer

下面的代码怎么样？我认为它的效率在最坏的情况下并不好，但它的预期效率会很好。

    int getFirstPole(int* a, int n)
{
    int leftPole = a[0];
    for(int i = 1; i < n; i++)
    {
        if(a[j] >= leftPole)
        {
            int j = i;
            for(; j < n; j++)
            {
                if(a[j] < a[i])
                {
                    i = j+1;  //jump the elements between i and j                   
                    break;
                }
                else if (a[j] > a[i])
                    leftPole = a[j];
            }
            if(j == n) // if no one is less than a[i] then return i
                return i;
        }
    }
    return 0;
}

algorithm - 面试 - 在数组中查找幅度极点

8 回答 8

Related

Reference