取K元素，最大化最小距离

本文介绍了取K元素，最大化最小距离的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

由于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]