我怎样才能(更)容易地比较两组数字

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

EDIT：我刚刚意识到你说过这些集合是硬编码的，有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中。

Answer 2

下面的伪代码怎么样？

Condition(A : Set, B : Set) : Bool =
Let a := max(A), b := min(B) In
// Namely, that each number in the first set is less than at least one number in the other set
If a <= b Then
// the next numbers in the first set must be less than a different number in the second set 
Condition(without(A, a), without(B, b))
Else
False
EndIf

其中没有(A，A)表示集合A减去集合{A}

Answer 3

似乎List比Set做得更好，因为您的示例包含重复的元素。简单地说：

1) 对这两个列表进行排序。

2) 修剪第二个列表中的前几个元素，直到第一个和第二个的大小相等。

3) 对于每个i，直接比较list1[i]和list2[i]。

代码：

import java.util.*;
class Main {
public static void main (String[] args) {
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
list1.add(3); list1.add(7); list1.add(7);
list2.add(8); list2.add(8); list2.add(2); list2.add(1); list2.add(5);
//algorithm:
Collections.sort(list1);
Collections.sort(list2);
List<Integer> list3 = list2.subList(list2.size() - list1.size(), list2.size());
System.out.println(list1.size() + " " + list3.size());
boolean pass = true;
for(int i = 0; pass && i < list1.size(); i++)
if(list1.get(i) >= list3.get(i))
pass = false;
System.out.println(pass);
}
}