In an interview it was asked to find non- common elements between two string arrays.
在一次采访中,人们被要求在两个字符串数组之间找到非常见的元素。
Eg: String a[]={"a","b","c","d"};
String b[]={"b","c"};
O/p should be a,d
I have answered to the question that in Java Set is implemented using HashTable. The code with Set is much simpler:
我回答了Java Set中使用HashTable实现的问题。使用Set的代码更简单:
String[] a = {"a","b","c","d"};
String[] b = {"b", "c"};
Set<String> set = new HashSet<>(a.length);
for(String s : a){
set.add(s);
}
for(String s : b){
set.remove(s);
}
return set;
now my query is that is there any other better approach to achieve this
现在我的问题是,有没有其他更好的方法来实现这一目标
6 个解决方案
#1
You can shorten the code by
您可以缩短代码
TreeSet set = new TreeSet(Arrays.asList(a));
set.removeAll(Arrays.asList(b));
#2
If [x,y], [x,z]
should yield [y,z]
here's what I suggest:
如果[x,y],[x,z]应该产生[y,z],这就是我的建议:
String[] a = {"a","b","c","d"};
String[] b = {"b", "c", "x"};
Set<String> set = new HashSet<>(Arrays.asList(a));
for (String s : new HashSet<>(Arrays.asList(b)) {
if (!set.add(s)) // if it's already present
set.remove(s); // remove it from the result
}
If on the other hand, [x,y], [x,z]
should yield [y]
, I would suggest
另一方面,如果[x,y],[x,z]应该产生[y],我建议
Set<String> set = new HashSet<>(Arrays.asList(a));
set.removeAll(Arrays.asList(b));
#3
In effect, this expands upon Jon Skeet's answer, but does so using Java 8's streams.
实际上,这扩展了Jon Skeet的答案,但使用Java 8的流程。
String[] result = Arrays.stream(a)
.filter((s) -> Arrays.stream(b).noneMatch(s::equals))
.toArray(String[]::new);
System.out.println(Arrays.toString(result));
The main tenants of the code are:
该代码的主要租户是:
- Filter out any element contained in A if and only if it does not exist in B (through the short-circuiting terminal operator
noneMatch
), checking if the element is equal to anything in that stream. - Collect the results to a
String[]
.
过滤掉A中包含的任何元素,当且仅当它在B中不存在时(通过短路终端运算符noneMatch),检查该元素是否等于该流中的任何元素。
将结果收集到String []。
Another approach using Set
, and again using streams:
使用Set的另一种方法,再次使用流:
Set<String> setA = new HashSet<>(Arrays.asList(a));
Set<String> setB = new HashSet<>(Arrays.asList(b));
String[] setResult = setA.stream()
.filter((s) -> !setB.contains(s))
.toArray(String[]::new);
The main issue with the non-Set code as pointed out was that it is quadratic time in the worst case. This code here takes advantage of the constant access time to Set#contains
, and should run in about linear time.
指出非Set代码的主要问题是在最坏的情况下它是二次时间。这里的代码利用了Set#contains的持续访问时间,并且应该在大约线性时间内运行。
#4
I would handle this in three steps:
我会分三步处理:
- Find all elements in
a
but notb
- Find all elements in
b
but nota
- Add those two sets together
查找a中的所有元素,但不是b
找到b中的所有元素但不是a
将这两个集合添加到一起
So for example:
例如:
Set<String> aSet = new HashSet<>(Arrays.asList(a));
Set<String> bSet = new HashSet<>(Arrays.asList(b));
Set<String> aNotB = new HashSet<>(aSet);
aNotB.removeAll(bSet);
Set<String> bNotA = new HashSet<>(bSet);
bNotA.removeAll(aSet);
Set<String> onlyOne = new HashSet<>(aNotB);
onlyOne.addAll(bNotA);
(The stream code in Java 8 may well make this simpler too...)
(Java 8中的流代码也可以使这更简单......)
The code could be made shorter if you don't mind modifying aSet
and bSet
, but I find this version easier to read.
如果您不介意修改aSet和bSet,可以缩短代码,但我发现这个版本更容易阅读。
#5
Try this:
String a[]={"a","b","c","d"};
String b[]={"b","c"};
List aLst = new ArrayList(Arrays.asList(a));
List bLst = new ArrayList(Arrays.asList(b));
aLst.removeAll(bLst);
System.out.println(aLst);
#6
If the strings are only English letters (or over a small alphabet.. even ASCII) I would rather use a boolean[] by char value instead of HashSets etc to somewhat improve performance.
如果字符串只是英文字母(或小字母......甚至是ASCII),我宁愿使用boolean [] by char值而不是HashSets等来稍微提高性能。
#1
You can shorten the code by
您可以缩短代码
TreeSet set = new TreeSet(Arrays.asList(a));
set.removeAll(Arrays.asList(b));
#2
If [x,y], [x,z]
should yield [y,z]
here's what I suggest:
如果[x,y],[x,z]应该产生[y,z],这就是我的建议:
String[] a = {"a","b","c","d"};
String[] b = {"b", "c", "x"};
Set<String> set = new HashSet<>(Arrays.asList(a));
for (String s : new HashSet<>(Arrays.asList(b)) {
if (!set.add(s)) // if it's already present
set.remove(s); // remove it from the result
}
If on the other hand, [x,y], [x,z]
should yield [y]
, I would suggest
另一方面,如果[x,y],[x,z]应该产生[y],我建议
Set<String> set = new HashSet<>(Arrays.asList(a));
set.removeAll(Arrays.asList(b));
#3
In effect, this expands upon Jon Skeet's answer, but does so using Java 8's streams.
实际上,这扩展了Jon Skeet的答案,但使用Java 8的流程。
String[] result = Arrays.stream(a)
.filter((s) -> Arrays.stream(b).noneMatch(s::equals))
.toArray(String[]::new);
System.out.println(Arrays.toString(result));
The main tenants of the code are:
该代码的主要租户是:
- Filter out any element contained in A if and only if it does not exist in B (through the short-circuiting terminal operator
noneMatch
), checking if the element is equal to anything in that stream. - Collect the results to a
String[]
.
过滤掉A中包含的任何元素,当且仅当它在B中不存在时(通过短路终端运算符noneMatch),检查该元素是否等于该流中的任何元素。
将结果收集到String []。
Another approach using Set
, and again using streams:
使用Set的另一种方法,再次使用流:
Set<String> setA = new HashSet<>(Arrays.asList(a));
Set<String> setB = new HashSet<>(Arrays.asList(b));
String[] setResult = setA.stream()
.filter((s) -> !setB.contains(s))
.toArray(String[]::new);
The main issue with the non-Set code as pointed out was that it is quadratic time in the worst case. This code here takes advantage of the constant access time to Set#contains
, and should run in about linear time.
指出非Set代码的主要问题是在最坏的情况下它是二次时间。这里的代码利用了Set#contains的持续访问时间,并且应该在大约线性时间内运行。
#4
I would handle this in three steps:
我会分三步处理:
- Find all elements in
a
but notb
- Find all elements in
b
but nota
- Add those two sets together
查找a中的所有元素,但不是b
找到b中的所有元素但不是a
将这两个集合添加到一起
So for example:
例如:
Set<String> aSet = new HashSet<>(Arrays.asList(a));
Set<String> bSet = new HashSet<>(Arrays.asList(b));
Set<String> aNotB = new HashSet<>(aSet);
aNotB.removeAll(bSet);
Set<String> bNotA = new HashSet<>(bSet);
bNotA.removeAll(aSet);
Set<String> onlyOne = new HashSet<>(aNotB);
onlyOne.addAll(bNotA);
(The stream code in Java 8 may well make this simpler too...)
(Java 8中的流代码也可以使这更简单......)
The code could be made shorter if you don't mind modifying aSet
and bSet
, but I find this version easier to read.
如果您不介意修改aSet和bSet,可以缩短代码,但我发现这个版本更容易阅读。
#5
Try this:
String a[]={"a","b","c","d"};
String b[]={"b","c"};
List aLst = new ArrayList(Arrays.asList(a));
List bLst = new ArrayList(Arrays.asList(b));
aLst.removeAll(bLst);
System.out.println(aLst);
#6
If the strings are only English letters (or over a small alphabet.. even ASCII) I would rather use a boolean[] by char value instead of HashSets etc to somewhat improve performance.
如果字符串只是英文字母(或小字母......甚至是ASCII),我宁愿使用boolean [] by char值而不是HashSets等来稍微提高性能。