在另一个更大的数组中查找数组

Question

我最近被要求为一份工作编写3个测试程序.它们只使用核心Java API和我选择的任何测试框架编写.应在适当情况下实施单元测试.

虽然我没有收到任何反馈,但我认为他们不喜欢我的解决方案(否则我会听到他们的意见),所以我决定在这里展示我的程序并询问这个实现是否可以被认为是好的,并且,如果没有,那么为什么呢？

为避免混淆,我现在只问第一个.

实现一个函数,在另一个更大的数组中查找数组.它应该接受两个数组作为参数,它将返回第一个数组首先出现的第一个数组的索引.例如,findArray([2,3,7,1,20],[7,1])应返回2.

我没有尝试找到任何现有的解决方案,而是想自己做.

可能的原因:1.应该是静态的.2.应该使用行注释而不是块注释.3.没有先检查空值(我知道,发现太晚了).4.？

更新:提出了
很多原因,我很难选择一个答案,因为很多答案都有很好的解决方案.正如@adietrich所提到的,我倾向于相信他们希望我展示核心API的知识(他们甚至要求编写函数,而不是编写算法).

我相信保证工作安全的最佳方法是提供尽可能多的解决方案,包括:1.使用Collections.indexOfSubList()方法实现,以表明我知道核心集合API.2.使用强力方法实施,但提供更优雅的解决方案.3.使用搜索算法实现,例如Boyer-Moore.4.使用System.arraycopy()和Arrays.equal()的组合实现.然而,它不是性能方面的最佳解决方案,它将显示我对标准数组例程的了解.

谢谢大家的答案!
更新结束.

这是我写的:

实际计划:

package com.example.common.utils;

/**
 * This class contains functions for array manipulations.
 * 
 * @author Roman
 *
 */
public class ArrayUtils {

    /**
     * Finds a sub array in a large array
     * 
     * @param largeArray
     * @param subArray
     * @return index of sub array
     */
    public int findArray(int[] largeArray, int[] subArray) {

        /* If any of the arrays is empty then not found */
        if (largeArray.length == 0 || subArray.length == 0) {
            return -1;
        }

        /* If subarray is larger than large array then not found */
        if (subArray.length > largeArray.length) {
            return -1;
        }

        for (int i = 0; i < largeArray.length; i++) {
            /* Check if the next element of large array is the same as the first element of subarray */
            if (largeArray[i] == subArray[0]) {

                boolean subArrayFound = true;
                for (int j = 0; j < subArray.length; j++) {
                    /* If outside of large array or elements not equal then leave the loop */
                    if (largeArray.length <= i+j || subArray[j] != largeArray[i+j]) {
                        subArrayFound = false;
                        break;
                    }
                }

                /* Sub array found - return its index */
                if (subArrayFound) {
                    return i;
                }

            }
        }

        /* Return default value */
        return -1;
    }

}

测试代码:

package com.example.common.utils;

import com.example.common.utils.ArrayUtils;

import junit.framework.TestCase;

public class ArrayUtilsTest extends TestCase {

    private ArrayUtils arrayUtils = new ArrayUtils();

    public void testFindArrayDoesntExist() {

        int[] largeArray = {1,2,3,4,5,6,7};
        int[] subArray = {8,9,10};

        int expected = -1;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArrayExistSimple() {

        int[] largeArray = {1,2,3,4,5,6,7};
        int[] subArray = {3,4,5};

        int expected = 2;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArrayExistFirstPosition() {

        int[] largeArray = {1,2,3,4,5,6,7};
        int[] subArray = {1,2,3};

        int expected = 0;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArrayExistLastPosition() {

        int[] largeArray = {1,2,3,4,5,6,7};
        int[] subArray = {5,6,7};

        int expected = 4;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArrayDoesntExistPartiallyEqual() {

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

        int expected = -1;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArrayExistPartiallyEqual() {

        int[] largeArray = {1,2,3,1,2,3,4,5,6,7};
        int[] subArray = {1,2,3,4};

        int expected = 3;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArraySubArrayEmpty() {

        int[] largeArray = {1,2,3,4,5,6,7};
        int[] subArray = {};

        int expected = -1;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArraySubArrayLargerThanArray() {

        int[] largeArray = {1,2,3,4,5,6,7};
        int[] subArray = {4,5,6,7,8,9,10,11};

        int expected = -1;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

    public void testFindArrayExistsVeryComplex() {

        int[] largeArray = {1234, 56, -345, 789, 23456, 6745};
        int[] subArray = {56, -345, 789};

        int expected = 1;
        int actual = arrayUtils.findArray(largeArray, subArray);

        assertEquals(expected, actual);
    }

}

Answer 1

"仅使用核心Java API"的要求也意味着他们想要看看你是否会重新发明轮子.因此,除了您自己的实现,您可以提供单行解决方案,只是为了安全:

public static int findArray(Integer[] array, Integer[] subArray)
{
    return Collections.indexOfSubList(Arrays.asList(array), Arrays.asList(subArray));
}

指出给出的示例包含无效的数组文字可能是也可能不是一个好主意.

Answer 2

Clean and improved code 

public static int findArrayIndex(int[] subArray, int[] parentArray) {
    if(subArray.length==0){
        return -1;
    }
    int sL = subArray.length;
    int l = parentArray.length - subArray.length;
    int k = 0;
    for (int i = 0; i < l; i++) {
        if (parentArray[i] == subArray[k]) {
            for (int j = 0; j < subArray.length; j++) {
                if (parentArray[i + j] == subArray[j]) {
                    sL--;
                    if (sL == 0) {
                        return i;
                    }

                }

            }
        }

    }
    return -1;
}