新鲜的面试题，大家帮忙

Question

面试题，大家帮我看看，有没有高效的算法：
编写一个函数，能从一个大的array里找出一个小的array，这个函数以这两个array为参数，返回要查找的array在大array出现的第一个下标，比如：search([4,5,6,1, 12], [6,1]) 返回 2另外如果需要util test,最好也写上大家写上自己的答案，我看看自己当时写的怎么样

Answer 1

这个用 KMP 算法
时间复杂度为 O( m + n); m, n 为两个参数的长度
如果楼主你写的是 O(m * n)的估计是过不了关了

Answer 2

下边是我用 KMP 算法 实现的
楼主你也晒晒你的代码让我等学习下撒
package com.keeya.answer.test;public class KMPtest { public static void main(String[] args) {
int[] arr1 = {4, 5, 6, 1, 12};
int[] arr2 = {6, 1};
System.out.println(kmpSearch(arr1, arr2));
}

// 当 mat 为 tar 的连续子集时， 返回 mat 中第一个元素在 tar 中的位置
// 否则 返回 -1；
public static int kmpSearch(int[] tar, int[] mat) {
int[] arr = new int[mat.length];
arr[0] = -1;
int i_arr = 0;
int j_arr = -1;
while (i_arr < arr.length - 1) {
if (j_arr == -1 || mat[i_arr] == mat[j_arr]) {
if (mat[++i_arr] != mat[++j_arr]) {
arr[i_arr] = j_arr;
} else {
arr[i_arr] = arr[j_arr];
}
} else {
j_arr = arr[j_arr];
}
}
int i = 0;
int j = 0;
while (i < tar.length && j < mat.length) {
if (j == -1 || tar[i] == mat[j]) {
i++;
j++;
} else {
j = arr[j];
}
}
if (j == mat.length)
return i - mat.length;
return -1;
}
}

Answer 3

public static void main(String args[]){
search(new int[]{4,5,6,1,12}, new int[]{6,1});
}

public static void search(int[] longArray,int[] shortArray){
String longArrayString = Arrays.toString(longArray).replaceAll("[\\[\\]]", "");
String shortArrayString = Arrays.toString(shortArray).replaceAll("[\\[\\]]", "");
int index = longArrayString.indexOf(shortArrayString);
if(index!=-1){
String priorString = longArrayString.substring(0,index);
System.out.println("第一个下标为"+(priorString.split(",").length-1));
}else{
System.out.println("没找到");
}

}

Answer 4

错了。。
你试试改成
search(new int[]{4,5,16,16,6,1,12}, new int[]{6,1});

Answer 5

 直接的Arrays.toString方式是不行的，比如
{1,2,34,5,6}-》123456
里面找
{2,3,4,5}-》2345
会“成功”找到，所以不能用。
要用这个方法，估计也得把分隔符搞上。

Answer 6

package com.test.t0916;public class Test4 { /**
 * @param args
 */
public static void main(String[] args) {
int[] var1 = new int[]{4,5,6,1,12,6,1,2,3,6,1,4,5,6,1};
int[] var2 = new int[]{6,1};
System.out.println(getIndex(var1,var2));
} /**
 * 返回小数组在大数组中出现位置的字符串，以逗号分隔.
 * @param var1
 * @param var2
 * @return
 */
private static String getIndex(int[] var1,int[] var2) {
StringBuffer result = new StringBuffer();
StringBuffer strB1 = new StringBuffer();
StringBuffer strB2 = new StringBuffer();
for(int i=0; i<var1.length; i++) {
strB1.append(var1[i]+",");
}
for(int i=0; i<var2.length; i++) {
strB2.append(var2[i]+",");
}
int index = 0;
do{
index = strB1.indexOf(strB2.toString(),index+strB2.length());
if(-1 != index) {
if(Integer.valueOf(index)%2 ==0 ){
result.append(Integer.valueOf(index)/2+",");
}else {
result.append((Integer.valueOf(index)-1)/2+",");
}
}
}while(index != -1);
if(result.toString().length() > 0){
return result.toString().substring(0, result.toString().length()-1);
}else {
return "";
}
}
}

Answer 7

你说错了System.out.println(Arrays.toString(new int[]{4,5,6,1,12}));这个的结果是[4, 5, 6, 1, 12]

Answer 8

我擦
刚才去看了 String 类的源代码
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;
}
居然用的是时间复杂度为 O(m * n); 的算法
话说 KMP 算法《数据结构》里都有讲
可以说是基础算法了
写java类库的程序员没这么差劲吧？

Answer 9

package CSDN;import java.util.*;public class CollectionDemo1 { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub int[] i1 = {4, 5, 6, 1, 12};
int[] i2 = {6, 1};
Collection1 col1 = new Collection1(i1);
Collection1 col2 = new Collection1(i2);

Collection temp1 = col1.ColAdd();
Collection temp2 = col2.ColAdd();

boolean b = temp1.containsAll(temp2);
if(b){
int num;
for(int j=0;j<i1.length;j++){
num = i1[j];
if(num==i2[0]){
System.out.println(j);
}
}
}
}}class Collection1{
int[] array;
Collection1(int[] arr){
this.array = arr;
}
Collection c1 = new ArrayList();
Collection ColAdd(){
for(int i=0;i<this.array.length;i++){
c1.add(this.array[i]);
}
return c1;
}
}
 汗我的好长

Answer 10

 不过楼主要求的大array小array必须是连续的？
{1,2,4,7,8}
{2,4}true
{2,7}false
要求要连续么？

Answer 11

   看看能用不 /**
     * 
     * @param a 大数组
     * @param b 小数组
     * @return  小数组在大数组中的第一个匹配的索引位置: -1没有找到
     */
    public static int search(int[] a, int[] b)
    {
        if (Arrays.equals(a, null) || Arrays.equals(b, null))
        {
            return -1;
        }
        
        int bFirst = b[0];
        int bLength = b.length;
        int aLength = a.length;
        
        for(int i = 0; i < aLength; i++)
        {
            if(bFirst == a[i])
            {
                int[] tempArray = new int[bLength];
                System.arraycopy(a, i, tempArray, 0, bLength);
                
                if(Arrays.equals(tempArray, b))
                {
                   return i; 
                }
            }
        }
        
        return -1;
    }

Answer 12

我也写了一个不知道对不对呀 大家帮我看看
public class a1 { /**
 * @param args
 */
public static void search(int[] max,int[] min){
int index=-1,count=0;
for(int i=0;i<max.length;i++){
if(max[i]==min[0]){
for(int j=1;j<min.length;j++){
if(max[i+j]==min[j]){
index=i;
}else{
count++;
}
}
}
}
if(count==0){
System.out.println(index);
}
}
public static void main(String[] args) {
// TODO 自动生成方法存根
int[] max={4,5,16,16,6,1,12};
int[] min={6,1};
search(max,min);
}}

Answer 13

我也写了一个不知道对不对呀 大家帮我看看
public class a1 { /**
 * @param args
 */
public static void search(int[] max,int[] min){
int index=-1,count=0;
for(int i=0;i<max.length;i++){
if(max[i]==min[0]){
for(int j=1;j<min.length;j++){
if((i+j)<max.length&&max[i+j]==min[j]){
index=i;
}else{
count++;
}
}
}
}
if(count==0){
System.out.println(index);
}else{
System.out.println("没有找到符合要求的下标");
}
}
public static void main(String[] args) {
// TODO 自动生成方法存根
int[] max={4,5,16,16,6,1,12};
int[] min={1,6,1};
search(max,min);
}}

Answer 14

感觉这种方法简单O(∩_∩)O~：import java.util.Arrays;public class TextCompare1 {

public static int compareAB(int[]a,int[]b) {
int index=-1;
for(int i=0;i<a.length;i++) {
if(a[i]==b[0]) {
index=i;
break;
}
}
if(index==-1) {
return -1;
}
Arrays.sort(a);
Arrays.sort(b);
for(int i=0;i<b.length;i++) {
         if(Arrays.binarySearch(a, b[i])==-1) {
          return -1;
         }
}
return index;
}
    public static void main(String args[]) {
     int a[]={4,5,6,1, 12};
     int b[]={6,1};
     System.out.println(compareAB(a,b));
    }
}
结果：2

Answer 15

我的比较基本啊 没用算法 也没用到string的subString来做package org.csdn.damon;public class FindArray {
public int findArray(int[] bigArray,int[] smallArray){
int index=-1;
int smallLength=smallArray.length;
if(smallLength>bigArray.length){
return -1;
}
while(true){
for(int i=0;i<(bigArray.length-smallArray.length);i++){
for(int j=0;j<smallLength;j++){
if(bigArray[i+j]==smallArray[j]){
if(j==smallLength-1){
index=i;
}
continue;
}else{
break;
}
}
}
break;
}
return index;
}
public static void main(String[] args){
int[] a={4,5,16,1,6,1,12};
int[] b={6,1};
FindArray find=new FindArray();
System.out.println(find.findArray(a, b));
}
}

Answer 16

应该不用多复杂哦，package com;import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class SearchArray { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
List l = Arrays.asList(1, 2, 6, 1, 3, 9, 0, 619);
List ll = Arrays.asList(6, 1);
System.out.println(Collections.indexOfSubList(l, ll));
}}

Answer 17

可是， 谁说过那两个array 一定是 int型的呢 。  换成别的类型这些都不能用了哇哇

Answer 18

偷懒写了个不咋滴的..public int findArrayIdx(){
int [] A = new int[]{1,2,34,5};
int [] B = new int[]{5,6};
Map<Integer, Integer> mapA = new HashMap<Integer, Integer>();
Map<Integer, Integer> mapB = new HashMap<Integer, Integer>();
for (int i = 0; i < A.length; i++) {
mapA.put(A[i], i);
}
for (int i = 0; i < B.length; i++) {
mapB.put(B[i], i);
} for (int i = 0; i <A.length; i++) {
if (mapB.get(A[i])!=null) {
return mapA.get(A[i]);
}
} return 0;
}

Answer 19

帅哥，你这个简单倒是简单就是不对，你处理数据不连续的试试，它返回的就是-1，如List l = Arrays.asList(4,5,6,1, 12);
        List ll = Arrays.asList(1,5,6);它执行返回-1，但是答案应该是1

Answer 20

没得问题哈，array和list的实现原来都是数组，都是有顺序的，所以[1,2,3]!=[1,3,2]

Answer 21

你试试我给你的那两组数据，List l = Arrays.asList(4,5,6,1, 12);
            List ll = Arrays.asList(1,5,6);；它返回的是-1

Answer 22

按数组的概念是返回-1，1，5，6你的意思是和5,6,1匹配吗？除非是set集合

Answer 23

private static int arrayContain(int[] source, int[] dest) {

int index = -1;
boolean flag = false;

for (int i = 0; i < source.length; i++) {

if (source[i] == dest[0]) {

index = i;

for (int j = 1; j < dest.length; j++) {

if ((i +j) < source.length && (source[i + j] == dest[j])) {

}else {
index = -1;
break;
}
flag = true;
}
}

if (flag == true) {
break;
}
}
return index;
}

Answer 24

import java.util.*;
public class Test {
public static void main(String[] args) {
int[] arr = new int[]{4,5,6,1,12};
int[] sub = new int[]{6,1};
new Test().compare(arr,sub);
} public void compare(int[] arr,int[] sub) {
List<Integer> temp = new ArrayList<Integer>();
int firstNum = -1;
int num = 0;
for(int i=0;i<arr.length;i++) {
if(sub.length >num  && sub[num] == arr[i]) {
if(temp.size()==0) {
firstNum = i;
}
if(sub.length > num) {
temp.add(sub[num]);
}

}
if(firstNum != -1) {
++num;
}
}
if(temp.size() == sub.length) {
System.out.println("找到拉!开始位置为"+firstNum);
for(int val:temp) {
System.out.print(val + " ");
}
}else{
System.out.println("抱歉没有找到！");
}

}
}时间复杂度为O(m)

Answer 25

public static void search(int[] arr1 , int[] arr2) {
int len1 = arr1.length;
int len2 = arr2.length;

int matchLen = 0;
if(len1 < len2) {
return ;
}
for(int i=0; i<len1;) {
for(int j=0; j<len2;) {
if(arr2[j++] == arr1[i++]) {
matchLen ++;
if(matchLen == len2) {
System.out.println("the position is "+(i-len2));
break;
}
}else {
i = i+matchLen;
matchLen = 0;
break;
}
}

}

}

Answer 26

public class KMPMethod {  public static void main(String[] args) {
      int[] arr1 = {4, 5,6,1, 12};
      int[] arr2 = {6, 1};
      //System.out.println(10/3);
     System.out.println(kmpSearch(arr1, arr2));
  }
  
//  当 mat 为 tar 的连续子集时， 返回 mat 中第一个元素在 tar 中的位置
//  否则 返回 -1；
  public static int kmpSearch(int[] tar, int[] mat) {
      int result = -1;
      for(int i=0;i<tar.length;i++){
       int index = 0;
       for(index=0;index<mat.length;index++){
       if(tar[index+i]!=mat[index]) break;
       }
       if(index==mat.length){
       result = i;
       }
      }
   return result;
  }
}大家看看有什么问题

Answer 27

lastIndexOfSubList(List<?> source, List<?> target) 返回指定源列表中最后一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1。

Answer 28

indexOfSubList(List<?> source, List<?> target) 
  
返回指定源列表中第一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1。

Answer 29

代码有BUG 
你拿下边这个测试下int[] arr = new int[]{4,5,-1,6,3,1,12,6,1};
        int[] sub = new int[]{6,1};

Answer 30

帅哥不是结果=2，就是对的，你代码有bug！没理解LZ的意思

Answer 31

public static int find(int[] aBig,int[] aSmall){
StringBuffer sbBig = new StringBuffer(Arrays.toString(aBig));
StringBuffer sbSmall = new StringBuffer(Arrays.toString(aSmall));
sbSmall.deleteCharAt(0).deleteCharAt(sbSmall.length()-1);

int result = (sbBig.indexOf(sbSmall.toString())-1)/3;
return result;

}
public static void main(String[] args) {
int[] a1={4,5,12,23,6,6,1,12};
int[] a2={6,1};
System.out.println(find(a1,a2));
}
现在基本上只能想到这种方法

Answer 32

KMP也学过的 只是现在又忘了 真是………………佩服keeya0416

Answer 33

这个有bug，你可以将23换为23333试试。

Answer 34

哥们，送给你一个归并算法设计的获取，他的时间复杂度为两个数组长度的最大值，
设计思路为在两个数组下各设计一个指针，比较这两个数组中元素的大小，小的指针向后移动一位，如果相等，则给一个计数器变量值赠1，并且两个数组的指针都后移这是我能发现的时间复杂度最小的算法。
public class Sum { /**
 * @归并方法
 */
public int search(int a[],int b[]){

int n = 0;
for(int i=0,j=0;i<a.length&&j<b.length;){
if(a[i]>b[j])
j++;
else if(a[i]<b[j])
i++;
else 
    {
n++;
i++;
j++;
    }
}
return n;
}


public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = new int[]{3,12,16,17,23,26,31};
int b[] = new int[]{4,16};
Sum s = new Sum();
int m = s.search(a,b);
        System.out.println("两个集合集合中共有的元素有"+m+"个");
}}