3

我有一个二维空间中的对象列表，每个对象当然都有一个 XY 位置和一个宽度和高度。

我想提取 N 个大小最相似的对象。

例如：

Size Object 1 : 100 (10 W x 10 H)

Size Object 2 : 150

Size Object 3 : 140

Size Object 4 : 160

Size Object 5 : 140

在这种情况下，对于 N = 4，返回列表将是：Objects: {2,3,4,5}

我的想法是计算平均大小并逐一获得最接近平均值的对象。但是，当有大物体使平均值上升时，这种方法就会失败。

有什么建议吗？

谢谢你们！

4

2 回答 2

3

第一步是按大小对输入数组进行排序。然后，遍历数组，同时保持一组运行的“最相似”元素，但是您正在定义它。假设一组 N 个元素是“最相似的”，如果它最小化集合中最小元素和最大元素之间的差异，那么你的算法看起来像

Deque leastSet = new LinkedList(); // use a Deque instead of a Set because order is important, and presumably your inputArray doesn't contain duplicates anyway; if the input may contain duplicates, then use a LinkedHashSet instead
Deque currentSet = new LinkedList();

// initialize deques with first N elements
for(int i = 0; i < N; i++) {
    leastSet.addLast(inputArray[i]);
    currentSet.addLast(inputArray[i]);
}

for(int i = N; i < inputArray.length; i++) {
    currentSet.removeFirst();
    currentSet.addLast(inputArray[i]);
    if((currentSet.peekLast() - currentSet.peekFirst()) < (leastSet.peekLast() - leastSet.peekFirst())) {
        leastSet = currentSet.clone();
    }
}
于 2013-05-24T17:13:18.467 回答
0

蛮力将创建一组从 min val 到 max val 的桶（列表数组）。从 delta 1 开始。遍历每个元素并将其放入从 val - delta 到 val + delta 的每个桶中。确定任何桶是否有 n 个元素。如果不是将增量增加一并重复。

另一个（可能是更好的选择）。按大小排序。从像 1 这样的小 maxdelta 开始。然后查看每个元素 (i) 和元素 (i+n)。如果 i & i+n 的 delta 小于 maxdelta，则这是您的集合（或至少是您的集合的开始，因为可能有其他元素）。如果不增加 i。如果没有找到设置增量 maxdelta 并重复。

于 2013-05-24T17:09:21.623 回答