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

最近我被要求写一个工作3个testing程序。 他们将只使用核心Java API和我select的任何testing框架来编写。 unit testing应在适当的地方执行。

虽然我还没有收到任何反馈，但我想他们不喜欢我的解决scheme（否则我会听到他们的），所以我决定在这里展示我的程序，询问这个实现是否可以被认为是好的，如果不是，那为什么？

为了避免混淆，我现在只会问第一个。

实现一个在另一个更大的数组中find数组的函数。 它应该接受两个数组作为参数，它将返回第一个数组第一个完全出现的第一个数组的索引。 例如，findArray（[2,3,7,1,20]，[7,1]）应该返回2。

我没有试图find任何现有的解决scheme，而是想自己做。

可能的原因：1.应该是静态的。 2.应该使用行注释，而不是块注释。 3.没有先检查空值（我知道，只是发现太晚了）。 4.？

更新 ：
有很多原因已经提出，我很难select一个答案，因为许多答案都有一个好的解决scheme。 正如@adietrich所提到的，我倾向于相信他们希望我展示核心API的知识（他们甚至要求编写一个函数，而不是写一个algorithm）。

我相信确保工作的最好方法是尽可能多的提供解决scheme，包括：1.使用Collections.indexOfSubList（）方法实现，以显示我知道核心集合API。 2.使用暴力方法实施，但提供更优雅的解决scheme。 3.使用searchalgorithm实现，例如Boyer-Moore。 4.使用System.arraycopy（）和Arrays.equal（）的组合来实现。 然而，在性能方面不是最好的解决scheme，它会显示我对标准数组例程的知识。

谢谢大家的回答！
更新结束。

这是我写的：

实际计划：

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; } } 

testing代码：

 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”的要求也意味着他们想看看你是否会重新发明。 所以除了自己的实现之外，你可以给出单线解决scheme，只是为了安全起见：

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

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

Answer 2

为了在更大的整数数组中find整数数组，可以使用与查找更大的string中的子串相同的algorithm。 为此有许多algorithm已知（见维基百科 ）。 特别是Boyer-Moorestringsearch对于大型arrays来说是高效的。 你试图实现的algorithm效率不高（维基百科称这是“天真”的实现）。

对于你的问题：

1. 是的，这样的方法应该是静态的
2. 不在乎，这是品味的问题
3. 可以包含null检查，或者您应该在JavaDoc中声明不允许使用null值，或者JavaDoc应该声明当任何参数为null时，将引发NullPointerException。

Answer 3

那么，从我的头顶上：

1. 是的，应该是静态的。

2. 抱怨这个公司不值得为之工作。

3. 是的，但是你会怎么做？ 返回？ 或抛出exception？ 它会抛出一个exception，它已经是这样了。

4. 我认为主要的问题是你的代码不是很优雅。 内循环中检查太多。 太多的重复检查。

只是生，离我的头顶：

 public int findArray(int[] largeArray, int[] subArray) { int subArrayLength = subArray.length; if (subArrayLength == 0) { return -1; } int limit = largeArray.length - subArrayLength; int i=0; for (int i = 0; i <= limit; i++) { boolean subArrayFound = true; for (int j = 0; j < subArrayLength; j++) { if (subArray[j] != largeArray[i+j]) { subArrayFound = false; break; } /* Sub array found - return its index */ if (subArrayFound) { return i; } } /* Return default value */ return -1; } 

你可以保留第一个元素的检查，所以你没有为数组中的每个元素设置布尔值和for循环的开销。 那么你会看着

 public int findArray(int[] largeArray, int[] subArray) { int subArrayLength = subArray.length; if (subArrayLength == 0) { return -1; } int limit = largeArray.length - subArrayLength; int i=0; for (int i = 0; i <= limit; i++) { if (subArray[0] == largeArray[i]) { boolean subArrayFound = true; for (int j = 1; j < subArrayLength; j++) { if (subArray[j] != largeArray[i+j]) { subArrayFound = false; break; } /* Sub array found - return its index */ if (subArrayFound) { return i; } } } /* Return default value */ return -1; } 

Answer 4

以下是使用KMP模式匹配algorithm的一种方法。 这个解决scheme需要O（n + m）。 其中n =大arrays长度，m =子arrays长度。 有关更多信息，请查看https://en.wikipedia.org/wiki/KMP_algorithm蛮力需要O（n m）。 我刚刚检查了Collections.indexOfSubList方法也是O（n m）。

 public static int subStringIndex(int[] largeArray, int[] subArray) { if (largeArray.length == 0 || subArray.length == 0){ throw new IllegalArgumentException(); } if (subArray.length > largeArray.length){ throw new IllegalArgumentException(); } int[] prefixArr = getPrefixArr(subArray); int indexToReturn = -1; for (int m = 0, s = 0; m < largeArray.length; m++) { if (subArray[s] == largeArray[m]) { s++; } else { if (s != 0) { s = prefixArr[s - 1]; m--; } } if (s == subArray.length) { indexToReturn = m - subArray.length + 1; break; } } return indexToReturn; } private static int[] getPrefixArr(int[] subArray) { int[] prefixArr = new int[subArray.length]; prefixArr[0] = 0; for (int i = 1, j = 0; i < prefixArr.length; i++) { while (subArray[i] != subArray[j]) { if (j == 0) { break; } j = prefixArr[j - 1]; } if (subArray[i] == subArray[j]) { prefixArr[i] = j + 1; j++; } else { prefixArr[i] = j; } } return prefixArr; } 

Answer 5

 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; } 

Answer 6

 int findSubArr(int[] arr,int[] subarr) { int lim=arr.length-subarr.length; for(int i=0;i<=lim;i++) { int[] tmpArr=Arrays.copyOfRange(arr,i,i+subarr.length); if(Arrays.equals(tmpArr,subarr)) return i; //returns starting index of sub array } return -1;//return -1 on finding no sub-array } 

更新：

通过重用相同的int数组实例：

 int findSubArr(int[] arr,int[] subarr) { int lim=arr.length-subarr.length; int[] tmpArr=new int[subarr.length]; for(int i=0;i<=lim;i++) { System.arraycopy(arr,i,tmpArr,0,subarr.length); if(Arrays.equals(tmpArr,subarr)) return i; //returns starting index of sub array } return -1;//return -1 on finding no sub-array } 

Answer 7

以前发布的一点优化代码：

 public int findArray(byte[] largeArray, byte[] subArray) { if (subArray.length == 0) { return -1; } int limit = largeArray.length - subArray.length; next: for (int i = 0; i <= limit; i++) { for (int j = 0; j < subArray.length; j++) { if (subArray[j] != largeArray[i+j]) { continue next; } } /* Sub array found - return its index */ return i; } /* Return default value */ return -1; } 

Answer 8

我会build议以下改进：

• 使函数静态，以便您可以避免创build一个实例
• 外部循环条件可能是i <= largeArray.length-subArray.length ，以避免循环内的testing
• 删除largeArray[i] == subArray[0]的testing（ largeArray[i] == subArray[0] ）

Answer 9

这是来自string的#indexOf：

 /** * Code shared by String and StringBuffer to do searches. The * source is the character array being searched, and the target * is the string being searched for. * * @param source the characters being searched. * @param sourceOffset offset of the source string. * @param sourceCount count of the source string. * @param target the characters being searched for. * @param targetOffset offset of the target string. * @param targetCount count of the target string. * @param fromIndex the index to begin searching from. */ static int indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) { if (fromIndex >= sourceCount) { return (targetCount == 0 ? sourceCount : -1); } if (fromIndex < 0) { fromIndex = 0; } if (targetCount == 0) { return fromIndex; } char first = target[targetOffset]; int max = sourceOffset + (sourceCount - targetCount); for (int i = sourceOffset + fromIndex; i <= max; i++) { /* Look for first character. */ if (source[i] != first) { while (++i <= max && source[i] != first); } /* Found first character, now look at the rest of v2 */ if (i <= max) { int j = i + 1; int end = j + targetCount - 1; for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++); if (j == end) { /* Found whole string. */ return i - sourceOffset; } } } return -1; } 

Answer 10

首先给你可能的原因：

1. 是。 而类final与一个private构造函数。
2. 根本不应该使用这种评论。 代码应该是不言自明的。
3. 你基本上隐式检查null通过访问将引发NullPointerException的length字段。 只有在largeArray.length == 0和subArray == null的情况下，才会滑过。

更多潜在的原因：

• 这个类不包含数组操作的任何函数，与文档所说的相反。
• 该方法的文档非常稀疏。 它应该说明何时抛出哪些exception（例如NullPointerException ）以及如果没有find第二个数组或者它是否为空，那么返回值是期望的。
• 代码比需要更复杂。
  1. 为什么第一个要素的平等性如此重要，以至于得到自己的支票呢？
  2. 在第一个循环中，假定第二个数组将被find，这是无意的。
  3. 不需要的variables和跳转（ boolean和break ），进一步减less易读性。
  4. largeArray.length <= i+j不容易把握。 应该在循环前检查，提高一路上的performance。
  5. 我会交换subArray[j] != largeArray[i+j]的操作数。 对我来说似乎更自然。
  6. 总之太久了。
• testing代码缺less更多的边缘情况（ null数组，第一个数组为空，两个数组都是空的，第一个数组包含在第二个数组中，第二个数组包含多次等）。
• 为什么最后一个名为testFindArrayExistsVeryComplex ？

缺less的练习是数组参数的组件types的规范，分别是方法的签名。 无论组件types是原始types还是引用types，都会产生巨大的差异。 adietrich的解决scheme假设一个引用types（因此可以被进一步改进），我的假设是一个原始types（ int ）。

所以这里是我的注意力，集中在代码/无视文档和testing：

 public final class ArrayUtils { // main method public static int indexOf(int[] haystack, int[] needle) { return indexOf(haystack, needle, 0); } // helper methods private static int indexOf(int[] haystack, int[] needle, int fromIndex) { for (int i = fromIndex; i < haystack.length - needle.length; i++) { if (containsAt(haystack, needle, i)) { return i; } } return -1; } private static boolean containsAt(int[] haystack, int[] needle, int offset) { for (int i = 0; i < needle.length; i++) { if (haystack[i + offset] != needle[i]) { return false; } } return true; } // prevent initialization private ArrayUtils() {} } 

Answer 11

  byte[] arr1 = {1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 1, 3, 4, 56, 6, 7}; byte[] arr2 = {9, 1, 3}; boolean i = IsContainsSubArray(arr1, arr2); 

---

  public static boolean IsContainsSubArray(byte[] Large_Array, byte[] Sub_Array){ try { int Large_Array_size, Sub_Array_size, k = 0; Large_Array_size = Large_Array.length; Sub_Array_size = Sub_Array.length; if (Sub_Array_size > Large_Array_size) { return false; } for (int i = 0; i < Large_Array_size; i++) { if (Large_Array[i] == Sub_Array[k]) { k++; } else { k = 0; } if (k == Sub_Array_size) { return true; } } } catch (Exception e) { } return false; } 

Answer 12

番石榴代码：

 import javax.annotation.Nullable; /** * Ensures that an object reference passed as a parameter to the calling method is not null. * * @param reference an object reference * @param errorMessage the exception message to use if the check fails; will be converted to a * string using {@link String#valueOf(Object)} * @return the non-null reference that was validated * @throws NullPointerException if {@code reference} is null */ public static <T> T checkNotNull(T reference, @Nullable Object errorMessage) { if (reference == null) { throw new NullPointerException(String.valueOf(errorMessage)); } return reference; } /** * Returns the start position of the first occurrence of the specified {@code * target} within {@code array}, or {@code -1} if there is no such occurrence. * * <p>More formally, returns the lowest index {@code i} such that {@code * java.util.Arrays.copyOfRange(array, i, i + target.length)} contains exactly * the same elements as {@code target}. * * @param array the array to search for the sequence {@code target} * @param target the array to search for as a sub-sequence of {@code array} */ public static int indexOf(int[] array, int[] target) { checkNotNull(array, "array"); checkNotNull(target, "target"); if (target.length == 0) { return 0; } outer: for (int i = 0; i < array.length - target.length + 1; i++) { for (int j = 0; j < target.length; j++) { if (array[i + j] != target[j]) { continue outer; } } return i; } return -1; }