Converting Primitive int array to list

I am trying to solve the following problem. There are two arrays A of size 开发者_开发百科n and B of size n+1. A and B have all elements same. B has one extra element. Find the element.

My logic is to convert the array to list and check if each element in B is present in A.

But when I am using the primitive arrays my logic is not working. If I am using

Integer [] a ={1,4,2,3,6,5};
Integer [] b = {2,4,1,3,5,6,7};

My code is working fine.

public static void main(String [] args)
{
    int [] a ={1,4,2,3,6,5};
    int [] b = {2,4,1,3,5,6,7};     
    List<Integer> l1 = new ArrayList(Arrays.asList(a));
    List<Integer> l2 = new ArrayList(Arrays.asList(b));
    for(Integer i :l2)
    {
        if(!l1.contains(i))
        {
            System.out.println(i);
        }           
    }
}

And also My logic is O(n+1). Is there any better algo.

Thanks

The reason it is not working for primitive arrays, is that Arrays.asList when given an int[ ] returns a List<Integer[ ]> rather than a List<Integer>.

Guava has an answer to this in the Ints class. Is has an asList method that will take an int[ ] and return a List<Integer>

Update

int[] a = ...;
int[] b = ...;
List<Integer> aList = Ints.asList(a);
List<Integer> bList = Ints.asList(b);

The above will allow your code to work properly for int[ ] as it works for Integer[ ].

Check out Ints API

Calculate the sum of each array. Sum(B) - Sum(A) will give you the extra element in B.

The contains method of an ArrayList is in fact not so efficient. This allone has a runtime of O(n), so your algorithm has runtime O(n^2).

I suggest to put one array in a HashSet (with a contains() runtime of O(1)). You can leave the other array as it is and iterate through the array directly. Then your runtime is O(n).

Update: From the HashSet API doc:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

I think the default Integer hash function fullfills the requirements.

Just for interest because it would be a bit complex because of arrays concatenation operation, but another operations would take O(n)

1. Put both arrays into a single array
2. XOR items
3. All the same items will be self-removed and single element will be the last one.

Construct a single Set<Integer> object. Since a Set can't have duplicate elements, add all of A, then you can use the Add function to find the one entry that returns true in B. Nice and easy.

The fastest approach is to use int[], use Arrays.sort and merge the results. I suspect it homework, so I will leave the actual solution to yourself. This is O(n * log(n)) but the constant is lower than using wrapper objects and sets.

If you know the range of values is limited, you can use a BitSet. This would detect more than one difference and still be O(n)

If you know there is one and only one difference, compare the sums as @rossum suggests.

You could construct two Set<Integer> objects from your two arrays, and then use removeAll() to find the extra element.

P.S. Your method is not O(n) as you seem to think. For the overall method to be O(n), each iteration of the loop has to execute in constant time; I leave it as an exercise for the reader to figure out whether this is the case.

Only for those that are interested, solution typical to the logic of rossum. But in case wen we have big numbers then it could be possible to have some overflow issue.

The alg is simple, we start with w zero value and from once array we substract from another we add to it the elements, at the end we add our n+1 element.

This will work in O(n) (the n is n+1)

I assume that array b have more elements.

long result = 0;

for(int i =0; i < a.length; i++) {
    result -= a[i];
    result += b[i];
}

result += b[a.length];

And in the result we have our difference.

EDIT:

Even better solution proposed by harold, where we don't need to worry about memory.

int result = 0;

for(int i =0; i < a.length; i++) {
    result ^= a[i] ^ b[i];
}

result ^= b[a.length];

If you want to convert an int array (not Integer), use IntStream:

int[] arr = {15, 13, 7, 4, 1, 5, 19, 18, 7, 7, 12, 15};
List<Integer> arrayList = IntStream.of(arr).boxed().collect(Collectors.toList());
System.out.println(arrayList);