Java 如何找到缺失的数字，给定：两个数组作为输入，并找到第一个数组中存在但第二个数组中缺失的数字
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22434225/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
how to find missing number,given: two arrays as input, and find a number that is present in first array but is missing in second array
提问by Newinjava
How to find missing number?
如何找到丢失的号码？
Given: two arrays as input, and find a number that is present in first array but is missing in second array.
给定：两个数组作为输入，并找到第一个数组中存在但第二个数组中缺失的数字。
public class Array2
{
public void missingnos(int a[],int b[])
{
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[i]>a[j])
{
int c=a[i];
a[i]=a[j];
a[j]=c;
}
}
System.out.print(a[i]);
}
for(int i=0;i<b.length;i++)
{
for(int j=i+1;j<b.length;j++)
{
if(b[i]>b[j])
{
int c=b[i];
b[i]=b[j];
b[j]=c;
}
}
System.out.print(b[i]);
}
int d[]=new int[a.length];
d=b;
int missing=0;
for(int i=0;i<b.length;i++)
{
if(a[i]!=d[i])
{
missing=a[i];
break;
}
}
System.out.println();
System.out.print(missing);
}
public static void main(String[] args) {
Array2 a2= new Array2();
int a[]={1,4,3,5,6};
int b[]={4,1,5,3};
a2.missingnos(a,b);
}
}
Test Case:when I remove 6 & 3 from array "a" and "b" respectively I get answer as 3 which is correct, but when i don't remove i get answer as 0.
测试用例：当我分别从数组“a”和“b”中删除 6 和 3 时，我得到的答案为 3，这是正确的，但是当我不删除时，我得到的答案为 0。
Why is it so?
为什么会这样？
采纳答案by JB Nizet
Your main problem is that you're trying to do it in a too complex way, and to do everything inside a single method. Sorting the arrays is not necessary, and doing it as you're doing is very inefficient, and doesn't use the Arrays.sort()method that would do it for you.
你的主要问题是你试图以一种过于复杂的方式来做，并在一个单一的方法中完成所有的事情。对数组进行排序是没有必要的，并且按照您的方式进行排序非常低效，并且不使用Arrays.sort()可以为您完成的方法。
Try to split the problem into simple tasks:
尝试将问题拆分为简单的任务：
- Find if a number is present in an array. That should be a method (
boolean isPresent(int number, int[] array)). - Iterate through the first array, and for each element, find if it's present in the second one. That should be your main method, using the first one:
- 查找数组中是否存在数字。那应该是一个方法（
boolean isPresent(int number, int[] array)）。 - 遍历第一个数组，对于每个元素，查找它是否存在于第二个数组中。这应该是你的主要方法，使用第一个：
.
.
public class Arrays2 {
public static void main(String[] args) {
int[] a = {1, 4, 3, 5, 6};
int[] b = {4, 1, 5, 3};
findMissingNumber(a, b);
}
private static void findMissingNumber(int[] a, int[] b) {
for (int n : a) {
if (!isPresent(n, b)) {
System.out.println("missing number: " + n);
break;
}
}
}
private static boolean isPresent(int n, int[] b) {
for (int i : b) {
if (n == i) {
return true;
}
}
return false;
}
}
回答by Aseem Goyal
for(int i=0;i<b.length;i++)
{
if(a[i]!=d[i])
{
missing=a[i];
break;
}
}
should be changed tofor(int i=0;i<min(a.Length,b.length);i++)because you are not handling case when size of both arrays are not same .
应该更改为for(int i=0;i<min(a.Length,b.length);i++)因为当两个数组的大小不同时您没有处理情况。
Also
还
int d[]=new int[a.length]; d=b;
int d[]=new int[a.length]; d=b;
what if length(b)>length(a)?
You have many errors , first try to work it on pen and paper , then transform into code .
万一length(b)>length(a)呢？
你有很多错误，先试着在笔和纸上工作，然后转化为代码。
回答by Vinod Satpute
When you have different sized arrays, then you need to stop as soon as one array reaches to its max position. Here you are getting answer as 0 because the b array has only 4 elements.
当您有不同大小的数组时，您需要在一个数组到达其最大位置时立即停止。在这里你得到的答案是 0，因为 b 数组只有 4 个元素。
The correct code is:
正确的代码是：
int d[]=new int[a.length];
d=b;
int missing=0;
for(int i=0;i<a.length;i++)
{
if(i>=b.length || a[i]!=d[i])
{
missing=a[i];
break;
}
}
System.out.println();
System.out.print(missing);
回答by vikeng21
you have complicated your logic. why use a 2nd combination of for loops when you could have done the comparison in the first for loop itself. you just need to display the numbers from the 1st array that are not present in 2nd array right
你的逻辑复杂了。当您可以在第一个 for 循环本身中进行比较时，为什么要使用第二个 for 循环组合。您只需要显示第一个数组中第二个数组中不存在的数字
回答by Puru--
Think about this as a problem of efficient algorithm. Using nested loops on arrays will give you a O(n^2) time complexity which is not desired.
将此视为有效算法的问题。在数组上使用嵌套循环会给你一个 O(n^2) 的时间复杂度，这是不想要的。
However if you use something like a HashSet your time complexity will be O(m+n) where m being the length of first array and n being the length of second array.
但是，如果您使用 HashSet 之类的东西，您的时间复杂度将为 O(m+n)，其中 m 是第一个数组的长度，n 是第二个数组的长度。
Something like below
像下面这样
import java.util.ArrayList;
import java.util.HashSet;
public class MissingNumbers {
public static Integer[] missingNumbers(Integer[] firstArray,Integer[] secondArray) {
ArrayList<Integer> alDups = new ArrayList<Integer>();
int dupCount = 0;
HashSet<Integer> setOfSecondArr = new HashSet<Integer>();
// Add second array into hash set of integers
for (int i : secondArray) {
setOfSecondArr.add(i);
}
// Now add the first array, if it gets successfully added to the set
// it means second array did not have the number
for (int i : firstArray) {
if (setOfSecondArr.add(i)) {
alDups.add(i);
dupCount++;
}
}
return alDups.toArray(new Integer[dupCount]);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
for (int i : missingNumbers(new Integer[] { 1, 2, 3, 5, 6 },
new Integer[] { 1, 2, 4 })) {
System.out.println(i);
}
}
}
回答by RP-
I know this is an old question, but might help somebody. We don't really need to compare each and every element form first and second array..
我知道这是一个老问题，但可能会帮助某人。我们真的不需要比较第一个和第二个数组中的每个元素。
Just take the sums (in long to avoid the overflow) from each array and subtract one array's sum with other array's sum. And the result is the missing number.
只需从每个数组中取总和（避免溢出），然后用另一个数组的总和减去一个数组的总和。结果是丢失的数字。
回答by yetAnotherCoder
Here's a way to solve this problem in O(1) auxiliary space and O(n) time. The solution is subject to the below constraints:
1) arr2 has only one element missing from arr1.
2) arr2.length=arr1.length-1 OR arr2 has the missing element replaced by 0.
这是在 O(1) 辅助空间和 O(n) 时间内解决此问题的方法。该解决方案受以下约束：
1) arr2 仅缺少 arr1 中的一个元素。
2) arr2.length=arr1.length-1 OR arr2 将缺失的元素替换为 0。
Solution: Simply take xor of all the elements of the two arrays. The resulting integer is the answer
解决方案：只需对两个数组的所有元素进行异或。结果整数就是答案
Code:
代码：
public static void findMissing(){
// TODO Auto-generated method stub
int[] arr1={3,7,2,90,34};
int[] arr2={2,7,34,3};
int xor=0;
for(int i=0;i<arr1.length;i++){
xor^=arr1[i];
}
for(int i=0;i<arr2.length;i++){
xor^=arr2[i];
}
System.out.println("missing number: "+xor);
}
Why it works? Say arr1={1,2,3,4} and arr2={1,2,4}. Taking xor of all element =>
1^2^3^4^1^2^4
= (1^1)^(2^2)^(4^4)^3
= 0^0^0^3
=3
为什么有效？说 arr1={1,2,3,4} 和 arr2={1,2,4}。取所有元素的异或 =>
1^2^3^4^1^2^4
= (1^1)^(2^2)^(4^4)^3
= 0^0^0^3
=3
Another solution as proposed by RP-is also very good and solves this problem in the same space and time complexities, but there is a chance of an overflow while calculating sums.
RP-提出的另一种解决方案也很好，在相同的空间和时间复杂度下解决了这个问题，但是在计算和时有可能溢出。
回答by Nitin Sindhe
public class FindMissingNumbers {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i,j,size1,size2;
boolean flag=false;
Scanner sc = new Scanner(System.in);
System.out.println("Enter 1st array lenght");
size1=sc.nextInt();//input array size
int[] a=new int[size1];
System.out.println("Enter "+size1+" Values of 1st array");
for(i=0;i<size1;i++){
a[i]=sc.nextInt();//read first array list
}
System.out.println("Enter 2st array lenght");
size2=sc.nextInt();//input array size
int b[]=new int[size2];
System.out.println("Enter Values of 2st array");
for(i=0;i<size2;i++){
b[i]=sc.nextInt();//read second array list
}
System.out.println("Numbers which are not present in 1nd array");
for(i=0;i<size2;i++)
{
flag=false;
for(j=0;j<size1;j++)
{
if(a[j]==b[i])
{
break;
}
else if(a[j]!=b[j] && j==size1-1){
flag=true;
}
}
if(flag==true){
System.out.println(b[i]);
flag=false;
}
}
}
}
回答by Yoga Gowda
Diff([1,2,3,4] [1,2,3]) = [4]
Diff([1,2,2,2], [1,2]) = [2,2]
Diff([2, 2, 1, 2], [1,2]) = [2,2]
Diff([1,1,1,1,1,1,2,2,2,2,2,2], [1,1,2,2]) = [1,1,1,1,2,2,2,2]
public static void main(String[] args) {
int[] a = {1,2,3,4};
int[] b = {1,2,3};
Arrays.sort(a);// The sorting only required for input example 3.
Arrays.sort(b);//
List<Integer> listA = new ArrayList<>();
for( int i = 0; i < a.length; i++ ) {
if( i >= b.length ) {
listA.add(a[i]);
}
for( int j = i; j < b.length; j++ ) {
if( a[i] == b[j] || listA.contains(a[i])) {
break;
} else {
listA.add(a[i]);
}
}
}//end of for loop
System.out.println(listA);
}
With is algorithem, only example 4 won't work.
回答by ashish singh
Try this:
尝试这个：
static void Main(string[] args)
{
int[] a = {1, 4, 3, 5, 6};
int[] b = {4, 1, 5, 3};
for (int i = 0; i < a.Length; i++)
{
if(!b.Contains(a[i]))
{
Console.WriteLine("missing number: " +a[i]);
}
}
Console.ReadKey();
}
