CODEWITHSUNDEEP
java
user1841492
user1841492

Reputation: 171

Find same element in two array

I am trying to find the same element in two arrays, where the elements must have a maximum distance between them equal to k.

My two arrays (of different size and not sorted) A and B, k max distance.

This is what I have done, but I don't know where there is an error...

for (int i = 0; i<A.length; i++){
    for(int j = i; j < k || j < B.length; j++)
        if(A[i] == B[j]){
            //Print on console
            System.out.println(B[i]);
            j = k;
        }
    }
}

For example:

A[3,7,5,9,10,15,16,1,6,2] 
B[4,8,5,13,1,17,2,11] 
k=6

The output should be 5 1 2, but I don't know why, my program give me only 5 . Can anyone help me understand why?

Upvotes: 0

Views: 660

Answers (7)

Zhenhong Zhu
Zhenhong Zhu

Reputation: 9

def getSameItems(aList, bList):
    a_max = aList[0]
    b_max = bList[0]
    for item in aList:
        if item > a_max: a_max = item
    for item in bList:
        if item > b_max: b_max = item
    aList_counting = [0] * (a_max + 1)
    bList_counting = [0] * (b_max + 1)

    for item in aList: aList_counting[item] += 1
    for item in bList: bList_counting[item] += 1
    min_item = a_max if a_max < b_max else b_max
    sameList = []
    for i in range(min_item + 1):
        if aList_counting[i] > 0 and bList_counting[i] > 0:
            sameList.append(i)
    return sameList
aList = [1, 7, 2, 2, 8]
bList = [1, 2, 3, 7, 7, 9, 2, 8]
print getSameItems(aList, bList)
[1, 2, 7, 8]

The above code is used in the python language,I am Chinese,so my english is poor，and cannot provide rich code annotations,sorry..I suggest that you can use counting sorting ideas,I hope it will help you!

Upvotes: 0

SteveL
SteveL

Reputation: 3389

Well you are starting the j from i, so it will iterate only the items in B that are after the i element of A.

This may work

    for (int i = 0; i<A.length; i++){
        for(int j =Math.max(0, i-k) ; j < Math.min(B.length, i+k); j++){
            if(A[i] == B[j]){
                System.out.println(B[j]);
            }
        }
    }

Or:

    for (int i = 0; i<A.length; i++){
        for(int j = 0; j < B.lenght; j++){
            if(A[i] == B[j] && Math.abs(i-j)<=k){
                System.out.println(B[j]);
            }
        }
    }

Upvotes: 0

hcg
hcg

Reputation: 652

Try this:

for (int i = 0; i<A.length; i++){
            for(int j = 0; j < B.length; j++)
                if(A[i] == B[j] && Math.abs(j-i)<k){
                    //Print on console
                    System.out.println(B[j]);
                }
            }

Upvotes: 0

njzk2
njzk2

Reputation: 39386

I don't understand what k is supposed to do, but your approach is O(n^2), which is way too much.

Using sets, you can find the intersection quite easily :

Set<Integer> aSet = new HashSet<Integer>();
// Adding an element to a set is O(1), this addAll operation is therefore O(n)
Collections.addAll(aSet, A);

// This loop is also O(n), as contains is O(1)
for (int b : B) {
    if (aSet.contains(b)) {
        // this b int is in A and b
    }
}

Overall, this approach is O(n)

Edit

As for k, my understanding in what you are doing is that you are only testing that j < k, which explains why only 5 comes out. you need to test the distance between i and j which is tested by 

Math.abs(j-i) < k

Upvotes: 0

Gerret
Gerret

Reputation: 3046

Hmm you have a odd style to do that. Why you do j = i? If you do that, you do not iterate over all values.

That may help you. I tryed it out it should work:

    int[] a = {3,7,5,9,10,15,16,1,6,2};
    int[] b = {4,8,5,13,1,17,2,11};

    int k = 6;

    for (int i = 0; i < b.length; i++) {
        for (int j = 0; j < k || j < a.length; j++) {
            if (b[i] == a[j]) {
                System.out.println(a[j]);
            }
        }
    }

Upvotes: 0

erencan
erencan

Reputation: 3763

Here is the solution. I checked, it works.

Your errors

  • Your second loop initialization and stopping condition is wrong. It should start from i - k (if it is less than 0, then it should start 0) and stop when j exceeds i + k. Second loop should run between i - k and i + k in array bounds.
  • You unconditionally set second loop variable to k which result unexpected behavior. Loop may go back a old value which result as infinite loop.
  • You control B[j] value, but print B[i] value. Which may cause array out of bound exception.

int[] a = { 3, 7, 5, 9, 10, 15, 16, 1, 6, 2 }; int[] b = { 4, 8, 5, 13, 1, 17, 2, 11 }; int k = 6;

    for (int i = 0; i < a.length; i++) {
        for (int j = ((i - k) < 0 ? 0 : i - k); j < i + k && j < b.length; j++) {

        if (a[i] == b[j]) {
            System.out.println(b[j]);
        }
    }  

    }

Upvotes: 0

oddparity
oddparity

Reputation: 436

for (int i = 0; i < A.length; i++) {
    int startIndex = Math.max(i - k + 1, 0);
    int endIndex = Math.min(i + k, B.length);
    for (int j = startIndex; j < endIndex; j++){
        if (A[i] == B[j]) {
            System.out.println(B[j]);
        }
    }
}

Uh, oh, not sure how you want the distance exactly, including the current element or excluding it. Also duplicates (in the same range) might be a special case to handle.

Upvotes: 1

Related Questions