取K元素，最大化最小距离 [英] Take K elements and maximise the minimum distance

问题描述

由于N个元素，我们可以取K位置出N的数组，但我们需要选择在这样一个用K的位置，如果我们采取任何两个选择的位置说，i和j比最小差异（A [我] -A [j]的）的所有对i和j属于至K choosen索引应为最大尽可能

示例

让N = 3和阵列= [3 9 6 11 15 20 23和K = 3

那么这里的答案是8作为一种可能的方式是，我们可以选择[3,11,23]或[3,15,23]

我只是想知道可以自己有些贪婪之类的对于这个问题的方法呢？或O（N），或O（N *日志N）的排序方法？

我知道这蛮力解决方案。但我不认为它张贴在这里将是不错的主意，因为它的效率非常低。

约束

  1≤N≤10 ^ 5
1≤ķ≤10 ^ 7
 

解决方案

  1。排序号码
2.选取前两个数字，它们之间最大的区别。
3.对于i = 3到k
   3.1选择具有最大差数
 

示例

  1。 [3 6 9 11 15 20 23]  - ＆GT; [3 6 9 11 15 20 23]
2.【3月23日]
3.选择11或15
 

复杂性= O（N日志N） [（K + N）的日志N]

Given an array of N elements we can choose K positions out of N. But we need to choose K positions in such a way that if we take any of the two chosen positions say i and j than minimum difference (A[i]-A[j]) for all pair of i and j belonging to K choosen indexes should be as maximum as possible.

Example :

Let N=3 and array be = [3 9 6 11 15 20 23 ] and K=3

then here answer is 8 as one possible way is we can choose [3,11,23] or [3,15,23]

I just want to know can their be some greedy sort of approach for this problem ? Or a O(N) or O(N*log N) sort of approach ?

I know brute solution for it. But I don't think posting it here would be good idea as its very inefficient.

Constraints :

1 ≤ N ≤ 10^5
1 ≤ K ≤ 10^7

解决方案

1. Sort the numbers
2. Pick first two numbers with maximum difference between them.
3. For i = 3 to k
   3.1 Pick the number that has maximum difference

Example

1. [3 9 6 11 15 20 23] -> [3 6 9 11 15 20 23]
2. [3 23]
3. Pick 11 or 15

Complexity = O(N log N) [(k+N) log N]

这篇关于取K元素，最大化最小距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！