java - 我如何(更)轻松地比较两组数字？

Question

我有一组三个数字，我想将一组数字与另一组数字进行比较。即，第一组中的每个数字小于另一组中的至少一个数字。需要注意的是，第一组中的下一个数字必须小于第二组中的不同数字(即，{6,1,6} 对 {8,8,2} 有效，但 {6,2,6} 对 {8,8,2} 无效)。我有一个工作方法，但它很暴力而且丑陋。

如果我们有 setA 和 setB，并且每个都有元素 a、b 和 c:

if(setB.a < setA.a)
    if(setB.b < setA.b)
        if(setB.c < setA.c)
            return true;
    else if(setB.b < setA.c)
        if(setB.c < setA.b
            return true;

等等...

Answer 1

编辑:我刚刚意识到你说这些集合被硬编码为 3 个值。这是适用于任何大小的集合的超通用算法。

对于 3 值集合，您可以对集合元素进行相同的转储和排序，然后执行以下操作:

if(setB.a < setA.a)
    if(setB.b < setA.b)
        if(setB.c < setA.c)
            return true;
return false;

==========================================================

通用算法:

这是我立即想到的最有效的方法。

伪代码(比java更Python化，抱歉——希望注释能够解释):

list l1 = set1.items() //get the items out
list l2 = set2.items()

l1 = sort(l1)
l2 = sort(l2) //sort the lists

int set2idx1 = l1[0].find_closest_greater_than_value(l2) //binary search or something
if set2idx1 exists:
    l2 = l2[set2idx1+1:] //in python this means l2 is reassigned to a subarray of l2 starting at set2idx1+1 going to the end of l2
else:
    return false

for(int i=1; i<l1.len; i++)
    int set2idxi = l1[i].find_closest_greater_than_value(l2) //binary search or something
    if set2idxi exists:
        l2 = l2[set2idxi+1:]
    else
        return false

return true

如果有什么不明白的地方请评论

编辑编辑:

对任何感兴趣的各方的通用算法的解释:

1. 将集合元素转储到数组中
2. 对这些数组进行排序
3. 迭代第一个数组，查看第二个数组中是否有大于当前值的值。如果是这样，获取该值的索引，并删除之前的所有内容(包括该索引)，并将第二个数组变量重新分配给剩余的内容。
4. 如果不存在这样的值(因为它不存在或者您已经用完要测试的值，则返回 false)。否则，最后返回 true。

这里的想法是，由于数组已排序，您知道任何大于第二个数组中匹配元素的元素都将大于您在第一个数组中测试的元素。因此，您可以直接删除较低的值，并且由于您不想使用相同的值，因此您也可以删除找到的值。如果您返回 false，您知道这是因为没有更大的值，或者因为 array1 中的数字都大于 array2 中的数字，或者因为 array2 中没有足够的数字大于 array1 中的数字。