1

编辑

刚刚指出需求状态峰值不能是数组的末端。

所以我跑过这个网站

http://codility.com/

如果您能在 2 小时内解决这些问题，这会给您带来编程问题并为您提供证书。第一个问题是我以前见过的，通常称为峰与旗问题。如果你不熟悉

给出了一个由 N 个整数组成的非空零索引数组 A。一个峰值是一个数组元素，它比它的邻居大。更准确地说，它是一个索引 P 使得

0 < P < N - 1 和 A[P - 1] < A[P] > A[P + 1]

. 例如下面的数组 A：

A[0] = 1 
A[1] = 5 
A[2] = 3 
A[3] = 4 
A[4] = 3 
A[5] = 4 
A[6] = 1 
A[7] = 2 
A[8] = 3 
A[9] = 4 
A[10] = 6 
A[11] = 2

恰好有四个峰：元素 1、3、5 和 10。

您将前往一系列山脉，其相对高度由数组 A 表示。您必须选择随身携带的旗帜数量。目标是根据某些规则在峰上设置最大数量的标志。

标志只能设置在峰上。更重要的是，如果你取K个标志，那么任何两个标志之间的距离应该大于或等于K。索引P和Q之间的距离是绝对值|P-Q|。

例如，给定上面数组 A 表示的山脉，N = 12，如果你取：

两个标志，您可以将它们设置在峰 1 和 5 上；

三个标志，您可以将它们设置在峰 1、5 和 10 上；

四个标志，您只能在峰 1、5 和 10 上设置三个标志。

因此，在这种情况下，您最多可以设置三个标志。

编写一个函数，给定一个由 N 个整数组成的非空零索引数组 A，返回可以在数组峰值上设置的最大标志数。例如，给定上面的数组

如上所述，该函数应返回 3。

假使，假设：

N 是 [1..100,000] 范围内的整数；

数组 A 的每个元素都是 [0..1,000,000,000] 范围内的整数。

复杂：

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(N)，超出输入存储（不计算输入参数所需的存储）。

可以修改输入数组的元素。

所以这是有道理的，但我使用这段代码失败了

public int GetFlags(int[] A)
{
        List<int> peakList = new List<int>();
        for (int i = 0; i <= A.Length - 1; i++)
        {               
                if ((A[i] > A[i + 1] && A[i] > A[i - 1]))
                {
                    peakList.Add(i);
                }
        }

        List<int> flagList = new List<int>();
        int distance = peakList.Count;
        flagList.Add(peakList[0]);
        for (int i = 1, j = 0, max = peakList.Count; i < max; i++)
        {
            if (Math.Abs(Convert.ToDecimal(peakList[j]) - Convert.ToDecimal(peakList[i])) >= distance)
            {
                flagList.Add(peakList[i]);
                j = i;
            }
        }
        return flagList.Count;
}

编辑

int[] A = new int[] { 7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7 };

正确答案是 3，但我的应用程序说 2

这我不明白，因为有 4 个峰值（索引 1、4、6、8），因此，您应该能够在其中 2 个峰值（1 和 6）处放置一个标志

我在这里错过了什么吗？显然我的假设是 Array 的开头或结尾可以是一个峰值，不是这样吗？

如果这需要进入 Stack Exchange Programmers，我会移动它，但认为此处的对话框会有所帮助。

编辑

4

4 回答 4

2

显然我的假设是 Array 的开头或结尾可以是一个峰值，不是这样吗？

您的假设是错误的，因为峰值定义为：

0 < P < N - 1

对于第二个示例，您可以在 1、4、8 上设置 3 个标志。

于 2013-10-18T19:52:07.903 回答
0

这里有一个提示：如果可以设置 m 个标志，那么必须至少有 m * (m - 1) + 1 个数组元素。鉴于 N < 100,000，扭转上述情况应该让您相信问题可以被有效地暴力破解。

不，那是错误的。Codility 对定制解决方案进行了一系列测试，暴力破解很容易按时失败。

于 2013-10-31T10:18:13.063 回答
0

这里有一个提示：如果可以设置 m 个标志，那么必须至少有 m * (m - 1) + 1 个数组元素。鉴于 N < 100,000，扭转上述情况应该让您相信问题可以被有效地暴力破解。

于 2013-10-18T21:49:52.947 回答
0

我在这里给出了我的任务解决方案，该任务在 C++ 中实现了 100% 的代码（正确性和性能）。要理解给定索引距离的解决方案（例如，当第一个峰值从索引 2 开始，最后一个峰值从索引 58 开始时，距离为 56），其中包含 n 个峰值，最大数量有一个上限根据任务中描述的条件，可以保持标志的峰数。

#include <vector>
#include <math.h>

typedef unsigned int uint;

void flagPeaks(const std::vector<uint> & peaks,
    std::vector<uint> & flaggedPeaks,
    const uint & minDist)
{
    flaggedPeaks.clear();
    uint dist = peaks[peaks.size() - 1] - peaks[0];
    if (minDist > dist / 2)
        return;

    flaggedPeaks.push_back(peaks[0]);
    for (uint i = 0; i < peaks.size(); ) {
        uint j = i + 1;
        while (j < (peaks.size()) && ((peaks[j] - peaks[i]) < minDist))
            ++j;

        if (j < (peaks.size()) && ((peaks[j] - peaks[i]) >= minDist))
            flaggedPeaks.push_back(peaks[j]);
        i = j;
    }
}


int solution(std::vector<int> & A)
{
    std::vector<uint> peaks;
    uint min = A.size();
    for (uint i = 1; i < A.size() - 1; i++) {
        if ((A[i] > A[i - 1]) && (A[i] > A[i + 1])) {
            peaks.push_back(i);
            if (peaks.size() > 1) {
                if (peaks[peaks.size() - 1] - peaks[peaks.size() - 2] < min)
                    min = peaks[peaks.size() - 1] - peaks[peaks.size() - 2];
            }
        }
    }
    // minimal distance between 2 peaks is 2
    // so when we have less than 3 peaks we are done
    if (peaks.size() < 3 || min >= peaks.size())
        return peaks.size();

    const uint distance = peaks[peaks.size() - 1] - peaks[0];
    // parts are the number of pieces between peaks
    // given n + 1 peaks we always have n parts
    uint parts = peaks.size() - 1;
    // calculate maximal possible number of parts
    // for the given distance and number of peaks
    double avgOptimal = static_cast<double>(distance) / static_cast<double> (parts);
    while (parts > 1 && avgOptimal < static_cast<double>(parts + 1)) {
        parts--;
        avgOptimal = static_cast<double>(distance) / static_cast<double>(parts);
    }

    std::vector<uint> flaggedPeaks;
    // check how many peaks we can flag for the 
    // minimal possible distance between two flags
    flagPeaks(peaks, flaggedPeaks, parts + 1);
    uint flags = flaggedPeaks.size();
    if (flags >= parts + 1)
        return parts + 1;

    // reduce the minimal distance between flags
    // until the condition fulfilled
    while ((parts > 0) && (flags < parts + 1)) {
        --parts;
        flagPeaks(peaks, flaggedPeaks, parts + 1);
        flags = flaggedPeaks.size();
    }
    // return the maximal possible number of flags 
    return parts + 1;
}
于 2017-01-18T21:32:31.247 回答