小编典典

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

java

最近有人要求我为一份工作编写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);
    }

}

阅读 214

收藏
2020-09-08

共1个答案

小编典典

“仅使用核心Java API”的要求也可能意味着他们想看看您是否会重新发明轮子。因此,除了您自己的实现之外,为了安全起见,您还可以提供单线解决方案:

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

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

2020-09-08