How to find the occurence of an array in another array? and returning indexes of the first array

user_8716287 0
Viewed 1898

This is the algorithm I am trying to complete but don't know how to move forward ,

public int findArray(int[] array, int[] subArray) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; i < subArray.length; j++) {
            if (array[i] == subarray[j]) {//not sure if this is how to start 

            }
        }//will want to compare all element in subarray to Array
    }
    return 0;
}

My desired result would be as follows

//[4,9,3,7,8] and [3,7] should return 2.
//[7,8,9] and [8,9,10] should return -1

//[4,9,3,7,8,3,7,1] and [3,7]should return 5

My understanding is I take subarray as whole and try to find where it matches in the array but don't know how to go about it

arrays java
6 Answers

One simple approach: 

// 1) Convert array to String, for eg. [1,2,3,4] => "1234". 
// 2) Use Strings substring/lastIndexOf to find the correct index. 

private static int findSubarrayPosition(int[] array, int[] subarray) {
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < array.length; i++) {
          sb.append(array[i]);
      }
      String string = sb.toString();

      sb = new StringBuilder();
      for (int i = 0; i < subarray.length; i++) {
          sb.append(subarray[i]);
      }
      String subString = sb.toString();

      return string.lastIndexOf(subString);
}
user_8864650

Try following code. You have to check for first element in the sub array and then other elements.

public static int findArray(int[] array, int[] subArray) {
    int index = -1;
    arrayLoop : for (int i= 0; i<array.length; i++){
        if(array[i] == subArray[0]){
            for (int j=1; j<subArray.length; j++){
                if (i+j>array.length-1 || array[i+j]!=subArray[j]) continue arrayLoop;
            }
            index = i;
        }
    }
    return index;
}

Check your test cases with following code.

public static void main(String[] args) {
    int[] array1 = {4,9,3,7,8};  int[] subArray1 = {3,7};
    System.out.println(findArray(array1, subArray1));

    int[] array2 = {7,8,9};  int[] subArray2 = {8,9,10};
    System.out.println(findArray(array2, subArray2));

    int[] array3 = {4,9,3,7,8,3,7,1};  int[] subArray3 = {3,7};
    System.out.println(findArray(array3, subArray3));

}
user_37286390 
public static int findArray(int[] array, int[] subArray) {
    int count = 0;
    for (int i= 0; i < array.length; i++){
        for(int j=0; j < subArray.length; j++) {
          if(array[i] == subArray[j]){
              if(array.length > (i + 1) && subArray.length > (j + 1)) {
                    if(array[i + 1] == subArray[j + 1]) {
                        count += 1;
                        continue;
                    }
                }else if(subArray.length == j + 1) {
                        count += 1;
                        continue;
                    }
            }
        }
    }
    if(count < subArray.length) {
        return -1;
    }
    return count;
}

you can also do this

user_24941230

Here is the answer to the question:

public class FindInArray {

public static void main(String[] args) {

    int array[] = { 4, 5, 6, 7, 5, 8, 2, 3 };
    int subArray[] = { 2, 3 };

    System.out.println("Array position is: " + matcher(array, subArray));

}

public static int matcher(int[] array, int[] subArray) {

    int pos = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < subArray.length; j++) {
            if (array[i] != subArray[j]) {
                break;
            } else if (array[i] == subArray[j]) {
                boolean checkAllElements = compareRestElement(array, subArray, i, j);
                if (checkAllElements) {
                    pos = i;
                    return pos;
                } else {
                    pos = -1;
                }
            }
        }
    }

    return pos;
}

public static boolean compareRestElement(int[] arr, int[] subA, int index, int matchedPos) {
    boolean allElmentsOk = false;
    for (int k = matchedPos; k < subA.length; k++, index++) {
        if (arr[index] == subA[k]) {
            allElmentsOk = true;
            continue;
        } else {
            allElmentsOk = false;
        }
    }

    return allElmentsOk;
}

}

user_12204240

You can progressively shift comparison position, and find whichever sequence matches:

private static int findSubarrayPosition(int[] array, int[] subarray) {

    int start = 0;
    while (start + subarray.length < array.length) {
        if (Arrays.equals(Arrays.copyOfRange(array, start, start + subarray.length), subarray)) {
            return start;
        }

        start++;
    }

    return -1;
}

This can be tested using a call such as:

public static void main(String[] args) {

    int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int[] subarray = new int[] { 5, 6, 3 }; //returns -1
    int[] subarray = new int[] { 5, 6, 7 }; //returns 4

    System.out.println(findSubarrayPosition(array, subarray));
}

Then you know if it returns -1, you have no match; otherwise, the subarray was located at the returned index.

user_57615580 
 public class MyClass {
    public static void main(String args[]) {
    int array [] = {7,8,9};
     int subArray [] = {8,9,10};
   boolean isFirst = true;
    StringBuilder arrayBuilder = new StringBuilder();
    for(int i=0;i<array.length;i++){
        if(isFirst){
            arrayBuilder.append(array[i]);
            isFirst=false;
        }else{
               arrayBuilder.append(","+array[i]);
        }
    }
    isFirst=true;
    StringBuilder subArrayBuilder = new StringBuilder();
    for(int i=0;i<subArray.length;i++){
        if(isFirst){
            subArrayBuilder.append(subArray[i]);
            isFirst=false;
        }else{
               subArrayBuilder.append(","+subArray[i]);
        }
    }
    int occurence = arrayBuilder.toString().lastIndexOf(subArrayBuilder.toString());
    if(occurence!=-1){
       int commas = countNumberOfCommas(arrayBuilder.toString(),occurence);
       System.out.println("Exact Index:"+(occurence-commas)); 
    }else{
         System.out.println("Exact Index:"+(occurence)); 
    }

}

   public static int countNumberOfCommas(String input,int occurence){
      String []splitArray = input.substring(0,occurence).split(",");
      int count = splitArray.length;
      return count;

     }

}
user_86093940
Related