import java.util.*;
public class Main{
public static void main(String[] args) {
long startTime = System.currentTimeMillis();//获取当前时间
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();//nextLine（）方法返回的是Enter键之前的所有字符，它是可以得到带空格的字符串的。
List<String> lstString = new ArrayList<String>();
for (int i = 1; i <=m + n; i++) {
lstString.add(sc.nextLine());
}
List<String> lstend = new ArrayList<String>();
lstend = GetLst(lstString, n, m);
for (int i = 0; i < lstend.size(); i++) {
System.out.println(lstend.get(i));
}
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间："+(endTime-startTime)+"ms");
}
private static List<String> GetLst(List<String> lstString, int n, int m) {
// 把每行的句子拆分然后放到HashSet里面，前n个是查询库，后m个是被查询库
List<HashSet<String>> setList = new ArrayList<HashSet<String>>();// 所有HashSET放到一个集合中,一共n+m个
//setList.remove(0);
for (int i = 0; i <lstString.size(); i++) {
HashSet<String> stringSet = new HashSet<String>();// 把每行句子拆分的单词放到set集合，使其不重复
String[] s1 = lstString.get(i).split(" ");
stringSet.add(s1[0].toLowerCase());
for (int j = 1; j < s1.length; j++) {
stringSet.add(s1[j]);
}
setList.add(stringSet);
}
int[][] arraymn = new int[m][n];// 用来计数
for (int j = setList.size() - m; j < setList.size(); j++) {// 后m个被查询库
for (int i = 0; i < setList.size() - m; i++) {// 查询库
// tList.get(i).
Iterator<String> iter = setList.get(j).iterator();// setList.get(j)第j个HashSet
while (iter.hasNext()) {// 拿出第n个句子里单词匹配
String x = iter.next();
if (setList.get(i).contains(x)) {
arraymn[j - n][i]++;// 每有一个包含就计数一次,得到一个二维计数数组
}
}
}
}
List<String> lstEnd=new ArrayList<String>();
for (int i = 0; i < arraymn.length; i++) {
int max=0;int k=0;//用来获取最大值的下标
for (int j = 0; j < arraymn[i].length; j++) {
if(arraymn[i][j]>max)//拿到最大值的下标
{
max=arraymn[i][j];
k=j;
}
}
lstEnd.add(lstString.get(k));
}
return lstEnd;
}
}
你第一题时间复杂度为O（n^2）我发一个 O(n)的
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] array=new int[n];
for (int i = 0; i < n; i++) {
array[i] = sc.nextInt();// 输入十个数组
}
List<Integer> lst=new ArrayList<Integer>();
lst=GetIndex(array ,n);
if(lst.get(1)==-1)
{
System.out.println(-1);
}
else
{
System.out.println(lst.get(0)+" "+lst.get(1));
}
}
private static List<Integer> GetIndex(int[] array ,int n) {
int max=0;
int start=-1;
int end=-1;
List<Integer> updown=new ArrayList<Integer>();//将谷底点放入集合
if(array[1]>array[0])
updown.add(array[0]);//当第二项大于第一项添加进去
for (int i = 1; i <n-1; i++) {
if ((array[i]<array[i-1])&&(array[i]<array[i+1])) {
updown.add(i);//1-n-1之间波谷添加进去
}
}
if(array[n-1]<array[n-2])
updown.add(n-1);//当最后一项小于倒数第二项
for (int i = 0; i < updown.size()-1; i++) {
if((updown.get(i+1)-updown.get(i))>max)
{
max=updown.get(i+1)-updown.get(i);
start=updown.get(i);
end=updown.get(i+1);
}
}
List<Integer> lst=new ArrayList<Integer>();
lst.add(start);
lst.add(end);
return lst;
}
}
isaimawang
@ 赛码网
533869549