Java 如何在没有排序输出的情况下打印 2 个数组中的公共元素
How to print common elements in 2 arrays without sorted output in Java
给定两个数组,找出其中的公共元素。
示例:[1,45,33,23,22,45,233,21], [5,23,45,0,9,23,1,9]
=> 输出:[1,45, 23]
import java.io.*;
import java.util.*;
class Mycode {
public static void main(String args[]) {
int a[] = {1, 45, 33, 23, 22, 45, 233, 21};
int b[] = {5, 23, 45, 0, 9, 45, 1, 9};
Mycode test = new Mycode();
test.testNumber(a, b);
}
void testNumber(int c[], int d[]) {
System.out.println(Arrays.toString(c));
System.out.println(Arrays.toString(d));
Set<Integer> hset = new HashSet<Integer>();
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < d.length; j++) {
if (c[i] == d[j]) {
System.out.println(c[i]);
hset.add(c[i]);
}
}
}
System.out.println(hset);
}
}
实际输出:[1, 45, 33, 23, 22, 4, 233, 21] [5, 23, 45, 0, 9, 5, 1, 9]
=>
[1, 23, 45]
您可以使用
哈希表
遍历第一个数组并添加值为 false 的每个元素。
遍历第二个,如果它在 hashMap 中,那么它很常见。
像下面这样的东西怎么样?这样会更整洁,因为您不需要两个 for 循环,也不需要事先对其进行排序。
public class Mycode {
public static void main(String args[]) {
Integer a[] = {1, 45, 33, 23, 22, 45, 233, 21};
Integer b[] = {5, 23, 45, 0, 9, 45, 1, 9};
Mycode test = new Mycode();
System.out.println(test.testNumber(a, b));
}
public <T> Set<T> testNumber(T [] arra1, T [] arr2){
Set<T> set1 = new HashSet<T>();
Set<T> interset = new HashSet<T>();
Collections.addAll(set1, arra1);
for(T t: arr2){
if(set1.contains(t))
interset.add(t);
}
return interset;
}
}
HashSet 不保证保留 JavaDoc 中指示的插入顺序:
It makes no guarantees as to the iteration order of the set; in
particular, it does not guarantee that the order will remain constant
over time.
所以我更愿意使用 LinkedHashSet。此 Set 实现保证了插入顺序的保留。来自 JavaDocs:
This linked list defines the iteration ordering, which is the order in
which elements were inserted into the set (insertion-order)
void testNumber(int c[], int d[]) {
System.out.println(Arrays.toString(c));
System.out.println(Arrays.toString(d));
Set<Integer> hset = new LinkedHashSet<>();
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < d.length; j++) {
if (c[i] == d[j]) {
hset.add(c[i]);
}
}
}
System.out.println(hset);
}
输出:
[1, 45, 23]
List<Integer> list = new ArrayList<>(Arrays.asList(array1));
list.retainAll(Arrays.asList(array2));
System.out.println(list);
时间复杂度为 N 阶的解
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
// write your code here
Scanner scn = new Scanner(System.in);
int n1 = scn.nextInt();
int[] arr1 = new int[n1];
for (int i = 0; i < n1; i++) {
arr1[i] = scn.nextInt();
}
int n2 = scn.nextInt();
int[] arr2 = new int[n2];
for (int i = 0; i < n2; i++) {
arr2[i] = scn.nextInt();
}
HashMap < Integer, Integer > freqMap1 = new HashMap < > ();
for (int i = 0; i < n1; i++) {
int ch = arr1[i];
if (freqMap1.containsKey(ch)) {
int f = freqMap1.get(ch);
freqMap1.put(ch, f + 1);
} else {
freqMap1.put(ch, 1);
}
}
for (int i = 0; i < n2; i++) {
int ch = arr2[i];
if (freqMap1.containsKey(ch)) {
System.out.println(ch);
freqMap1.remove(ch);
}
}
}
}
给定两个数组,找出其中的公共元素。
示例:[1,45,33,23,22,45,233,21], [5,23,45,0,9,23,1,9]
=> 输出:[1,45, 23]
import java.io.*;
import java.util.*;
class Mycode {
public static void main(String args[]) {
int a[] = {1, 45, 33, 23, 22, 45, 233, 21};
int b[] = {5, 23, 45, 0, 9, 45, 1, 9};
Mycode test = new Mycode();
test.testNumber(a, b);
}
void testNumber(int c[], int d[]) {
System.out.println(Arrays.toString(c));
System.out.println(Arrays.toString(d));
Set<Integer> hset = new HashSet<Integer>();
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < d.length; j++) {
if (c[i] == d[j]) {
System.out.println(c[i]);
hset.add(c[i]);
}
}
}
System.out.println(hset);
}
}
实际输出:[1, 45, 33, 23, 22, 4, 233, 21] [5, 23, 45, 0, 9, 5, 1, 9]
=>
[1, 23, 45]
您可以使用 哈希表 遍历第一个数组并添加值为 false 的每个元素。 遍历第二个,如果它在 hashMap 中,那么它很常见。
像下面这样的东西怎么样?这样会更整洁,因为您不需要两个 for 循环,也不需要事先对其进行排序。
public class Mycode {
public static void main(String args[]) {
Integer a[] = {1, 45, 33, 23, 22, 45, 233, 21};
Integer b[] = {5, 23, 45, 0, 9, 45, 1, 9};
Mycode test = new Mycode();
System.out.println(test.testNumber(a, b));
}
public <T> Set<T> testNumber(T [] arra1, T [] arr2){
Set<T> set1 = new HashSet<T>();
Set<T> interset = new HashSet<T>();
Collections.addAll(set1, arra1);
for(T t: arr2){
if(set1.contains(t))
interset.add(t);
}
return interset;
}
}
HashSet 不保证保留 JavaDoc 中指示的插入顺序:
It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.
所以我更愿意使用 LinkedHashSet。此 Set 实现保证了插入顺序的保留。来自 JavaDocs:
This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order)
void testNumber(int c[], int d[]) {
System.out.println(Arrays.toString(c));
System.out.println(Arrays.toString(d));
Set<Integer> hset = new LinkedHashSet<>();
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < d.length; j++) {
if (c[i] == d[j]) {
hset.add(c[i]);
}
}
}
System.out.println(hset);
}
输出:
[1, 45, 23]
List<Integer> list = new ArrayList<>(Arrays.asList(array1));
list.retainAll(Arrays.asList(array2));
System.out.println(list);
时间复杂度为 N 阶的解
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
// write your code here
Scanner scn = new Scanner(System.in);
int n1 = scn.nextInt();
int[] arr1 = new int[n1];
for (int i = 0; i < n1; i++) {
arr1[i] = scn.nextInt();
}
int n2 = scn.nextInt();
int[] arr2 = new int[n2];
for (int i = 0; i < n2; i++) {
arr2[i] = scn.nextInt();
}
HashMap < Integer, Integer > freqMap1 = new HashMap < > ();
for (int i = 0; i < n1; i++) {
int ch = arr1[i];
if (freqMap1.containsKey(ch)) {
int f = freqMap1.get(ch);
freqMap1.put(ch, f + 1);
} else {
freqMap1.put(ch, 1);
}
}
for (int i = 0; i < n2; i++) {
int ch = arr2[i];
if (freqMap1.containsKey(ch)) {
System.out.println(ch);
freqMap1.remove(ch);
}
}
}
}