时间戳

首页 > 解决方案 > 算法：将元素分布在远离彼此的地方

algorithm - 算法：将元素分布在远离彼此的地方

问题描述

我有一个排序整数数组。给定一个整数 N，我需要将 N 个最大的元素放置得离彼此更远，以便它们之间有最大的空间。其余元素应放在这些大项目之间。例如，N=3 的 10 数组将导致 [0, 5, 8, 2, 6, 9, 3, 7, 10, 4]。

public static void main(String[] args) {
    int[] start = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int[] end = new int[10];
    int N = 4;
    int step = Math.round(start.length / N );
    int y = 0;
    int count = 0;

    for (int i = 0; i < step; i++) {
        for (int j = i; j<start.length; j = j + step) {
            //System.out.println(j + " " + i);
            if (count < start.length && start[count] != 0) {
                end[j] = start[count];
                count++;
            }
        }

    }
    System.out.println(end.toString());

}

标签： algorithmsorting

解决方案

你有一个K元素数组。您有N需要分配的最大数量。然后：

  1. Step := K/N（删除剩余部分）
  2. N从最大值取任意数字并将其插入Step/2位置。
  3. 取其他最大数，并在距离上一个插入的最大数之后插入Step。

给予[1,2,3,4,5,6,7,8,9,10]。所以K = 10，N = 3。然后Step = 3。所以第一个最大值放置在3/2位置

[1,10,2,3,4,5,6,7,8,9]

然后其他2的彼此3远离：

[1,10,2,3,9,4,5,8,6,7]

编码：

std::vector<int> Distribute(std::vector<int> aSource, int aNumber)
{
    auto step = aSource.size() / aNumber; // Note integer dividing.
    for (int i = 0; i < aNumber; ++i)
    {
        auto place = aSource.end() - i * step - step / 2;
        aSource.insert(place, aSource.front());
        aSource.erase(aSource.begin());
    }
    return aSource;
}

int main()
{
    std::vector<int> vec{10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10};
    auto res = Distribute(vec, 4);
    for (auto e : res)
    {
        std::cout << e << ", ";
    }
    std::cout << std::endl;
}

输出：

6, 5, 4, 7, 3, 2, 1, 0, 8, -1, -2, -3, -4, 9, -5, -6, -7, -8, 10, -9, -10,

推荐阅读