c++ - 如何使用 C/C++ 在数组中获取这样的范围？

Question

例如，有一个a大小为 10 的数组包含如下数据：

0.0
0.01
0.02
0.03
5.04
6.05
7.06
13.07
20.08
22.09

如果固定步长为 5，则预期数据范围为：

start   end
0.0     0.03
5.04    7.06
13.07   13.07
20.08   22.09

有什么建议可以在 C/C++ 中像这样实现它吗？如何编程？

Answer 1

#include <iostream>
using namespace std;

int fun(double* arr, int n, double* res)
{
    int start = 0;
    int end   = 0;
    int len   = 0;
    for(int i = start; i < n; ++i)
    {
        if(arr[i]- arr[end] < 5)
        {
            end = i;
        }
        else
        {
            res[len++] = arr[start];
            res[len++] = arr[end];
            start = end = i;
        }
    }
    res[len++] = arr[start];
    res[len++] = arr[end];
    return len;
}

int main()
{
    double t[] = { 
        0.0,
        0.01,
        0.02,
        0.03,
        5.04,
        6.05,
        7.06,
        13.07,
        20.08,
        22.09
    };

    int n = sizeof(t) / sizeof(*t);
    double *res = new double[n];
    int k = fun(t, n, res);
    for(int j = 0; j < k; j += 2)
        cout<<res[j]<<"  "<<res[j+1]<<endl;
 }

Answer 2

你可以在一个简单的循环中做到这一点：

#include <stdio.h>

int main(void)
{
    float f, a[] = {0.0, 0.01, 0.02, 0.03, 5.04, 6.05, 7.06, 13.07, 20.08, 22.09};
    size_t i;

    #define N (sizeof a / sizeof a[0])

    for (f = a[0], i = 0; i <= N; i++) {
        if (i == N || a[i] > f + 5.0) {
            printf("%f %f\n", f, a[i - 1]);
            if (i != N) f = a[i];
        }
    }
    return 0;
}

Answer 3

您可以使用一个简单的循环，保存最后的起始范围。C++ 中的一个简单实现：

#include <utility>
#include <vector>

vector<pair<size_t, size_t> > getRanges (vector<double> array)
{
    vector<pair<size_t, size_t> > result;
    size_t indexLastStart = 0;
    double valueLastStart = array[0];

    for (size_t i = 1; i < array.size(); i++)
    {
        if (array[i] - valueLastStart > 5.0)
        {
            result.push_back(make_pair(indexLastStart, i - 1));
            indexLastStart = i;
            valueLastStart = array[i];
        }
    }

    result.push_back(make_pair(indexLastStart, array.size() - 1));
    return result;
}

您可以按如下方式使用此功能：

int main()
{
    double t[] = { 
        0.0,
        0.01,
        0.02,
        0.03,
        5.04,
        6.05,
        7.06,
        13.07,
        20.08,
        22.09
    };
    vector<double> a(t, t + sizeof t / sizeof *t);
    vector<pair<size_t, size_t> > r = getRanges(a);

    for (size_t i = 0; i < r.size(); i++)
        cout << a[r[i].first] << "\t" << a[r[i].second] << endl;

    return 0;
}

在 C 中，它可能看起来像：

#include <stdio.h>

struct range
{
    int start;
    int end;
};

size_t getRanges(struct range *result, double *array, size_t inputSize)
{
    size_t outputSize = 0;
    size_t indexLastStart = 0;
    double valueLastStart = array[0];
    struct range added;
    size_t i;

    for (i = 1; i < inputSize; i++)
    {
        if (array[i] - valueLastStart > 5.0)
        {
            added.start = indexLastStart;
            added.end = i - 1;

            result[outputSize++] = added;
            indexLastStart = i;
            valueLastStart = array[i];
        }
    }

    added.start = indexLastStart;
    added.end = inputSize - 1;
    result[outputSize++] = added;
    return outputSize;
}

int main()
{
    double t[10] =
    { 
        0.0,
        0.01,
        0.02,
        0.03,
        5.04,
        6.05,
        7.06,
        13.07,
        20.08,
        22.09
    };
    struct range result[10];
    size_t i;
    size_t size = getRanges(result, t, sizeof t / sizeof *t);

    for (i = 0; i < size; i++)
    {
        printf("%.2f\t%.2f\n", t[result[i].start], t[result[i].end]);
    }

    return 0;
}

该算法以线性时间运行O(n)。

Answer 4

有点晚了，但无论如何这里是我对 C++ 的非常紧凑的实现。

template <typename T>
std::vector<std::pair<T, T>> generate_pairs(T *first, T *last)
{
    std::vector<std::pair<T, T>> result(std::distance(first, last) / 2);
    std::generate(std::begin(result), std::end(result), [&first] { return std::make_pair(*first++, *first++); });
    return result;
}

int main(int argc, char *argv[])
{
    double arr[] = { 0.0, 0.01, 0.02, 0.03, 5.04, 6.05, 7.06, 13.07, 20.08, 22.09 };

    auto v = generate_pairs(std::begin(arr), std::end(arr));
    for (const auto &p : v)
        std::cout << "(" << p.first << ", " << p.second << ")" << std::endl;

    return 0;
}

Answer 5

在 C# 中，您可以使用 List 在一行中轻松完成：

float[] subArray = new List<float>(myArray).GetRange(0, 8).ToArray();