k***t
发帖数: 276 | 1 Given a sorted array of n integers, pick up k elements so that the minimum
difference between consecutive elements is maximum (that is choose the
elements to maximize the quantity min(a[i+1] - a[i]))
==============================
Recursive backtracking? 不过好像是brute-force的方法。
感觉上是从n个柱子里选n-k个拔掉，选C(n, n-k)种里使k-1个区间中最小的最大。 |
i**d
发帖数: 357 | |
k***t
发帖数: 276 | 3 zkss?
【在 i**d 的大作中提到】
: binary search.
|
H***e
发帖数: 476 | 4 题目看着有奇异的，
举个例子吧，这样一目了然
【在 k***t 的大作中提到】
: Given a sorted array of n integers, pick up k elements so that the minimum
: difference between consecutive elements is maximum (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))
: ==============================
: Recursive backtracking? 不过好像是brute-force的方法。
: 感觉上是从n个柱子里选n-k个拔掉，选C(n, n-k)种里使k-1个区间中最小的最大。
|
k***t
发帖数: 276 | 5 例子如下，已加到原贴上了。
when k=2 the elements are a[0] and a[n-1]
when k=4, for example,
If the given array is (1,3,4,5,7)
If we choose (1,4,5,7) the min difference between elements is 1.
If we choose (1,3,5,7) the min difference is 2. So this k-set is the answer.
【在 H***e 的大作中提到】
: 题目看着有奇异的，
: 举个例子吧，这样一目了然
|
l*******0
发帖数: 176 | |
k***t
发帖数: 276 | 7 谢了。另外如何避免重复问。google search 问题关键字和mitbbs，没找到这个问题。
【在 l*******0 的大作中提到】
: 这个题在板上至少问过两次以上了。
: http://www.mitbbs.com/article/JobHunting/31959819_0.html
|
H***e
发帖数: 476 | 8 重复没有关系的吧
even better
这样大家都有机会学习啊。
【在 k***t 的大作中提到】
: 谢了。另外如何避免重复问。google search 问题关键字和mitbbs，没找到这个问题。
|
k***t
发帖数: 276 | 9 Isn't test() function use Greedy approach?
Can some one explain the reason why the greedy algorithm work?
Any link to algorithm explanation?
附Link上火鸡的Code:
http://www.mitbbs.com/article/JobHunting/31959819_0.html
Java code =>
public class MaxMinDiff {
public int max(int[] a, int k) {
int N = a.length;
if (N < k || k < 2) return -1;
int lo = 0;
int hi = (a[N-1] - a[0]) / (k-1) + 1;
while (hi > lo+1) {
int mid = (hi + lo) / 2;
if (test(a, mid, k)) {
lo = mid;
}
else {
hi = mid;
}
}
return lo;
}
private boolean test(int[] a, int diff, int k) {
int prev = a[0];
int j = 1;
for (int i=1; i
while (j
if (j >= a.length) return false;
prev = a[j];
}
return true;
}
【在 l*******0 的大作中提到】
: 这个题在板上至少问过两次以上了。
: http://www.mitbbs.com/article/JobHunting/31959819_0.html
|
k***t
发帖数: 276 | 10 考了一下古，是 下面问题的变种：
The Painter’s Partition Problem
http://www.leetcode.com/2011/04/the-painters-partition-problem.
answer.
【在 k***t 的大作中提到】
: Given a sorted array of n integers, pick up k elements so that the minimum
: difference between consecutive elements is maximum (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))
: ==============================
: Recursive backtracking? 不过好像是brute-force的方法。
: 感觉上是从n个柱子里选n-k个拔掉，选C(n, n-k)种里使k-1个区间中最小的最大。
|
