【第20天】给定一个数组，再给定q个询问，每次询问给定X，查找X的第一次出现的问题 | 哈希与穷举

• 序、专栏前言
• 一、【例题1】
• • 1、题目描述
  • 2、解题思路
  • 3、模板代码
  • 4、代码解析
• 二、【例题2】
• • 1、题目描述
  • 2、解题思路
  • 3、模板代码
  • • 1、HashMap
    • 2、数组哈希
  • 4、代码解析
• 三、推荐专栏
• 四、课后习题

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

  给定一个整数 n ( 1 ≤ n ≤ 1 e 5 ) n(1 leq n leq 1e5) n(1≤n≤1e5) ，然后输入 n n n个整数 ( 1 ≤ i ≤ n ) (1 leq i leq n) (1≤i≤n)，再给定一个整数 x x x，请你输出 x ( − 1 e 5 ≤ x ≤ 1 e 5 ) x(-1e5 leq x leq 1e5) x(−1e5≤x≤1e5)第一次出现的位置，如果不存在 x x x，输出 − 1 -1 −1。

  我们可以先将全部的数存入数组中，接收到 x x x后对整个数组进行遍历查询，也可以叫穷举。

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=sc.nextInt();
        }
        int x=sc.nextInt();
        for (int i = 0; i < n; i++) {
            if(a[i]==x){
                System.out.println(i+1);
                return;
            }
        }
        System.out.println(-1);
    }
}

• ( 1 ) (1) (1)注意题目中说明了下标是从 [ 1 , n ] [1,n] [1,n]，所以我们我们从下标为 0 0 0开始存储数据时，输出的下标应该加一。
• ( 2 ) (2) (2)当查找到 x x x后，输出答案后，就可以直接 r e t u r n return return结束程序，不会再执行后面的代码。当执行到最后说明没有找到 x x x，输出 − 1 -1 −1。最坏的情况下， x x x位于数组的末尾或者不存在 x x x，时间复杂度为 O ( n ) O(n) O(n)

  给定一个整数 n ( ( 1 ≤ x ≤ 1 e 5 ) ) n((1 leq x leq 1e5)) n((1≤x≤1e5)) ，然后输入 n n n个整数 ( 1 ≤ i ≤ n ) (1 leq i leq n) (1≤i≤n)，再给定 q ( 1 ≤ q ≤ 1 e 5 ) q(1 leq q leq 1e5) q(1≤q≤1e5)个询问，每次询问请你输出 x ( − 1 e 5 ≤ x ≤ 1 e 5 ) x(-1e5 leq x leq 1e5) x(−1e5≤x≤1e5)第一次出现的位置，如果不存在 x x x，输出 − 1 -1 −1。

  这题与上一题的区别在于有 q q q个询问，如果对于每个循环我们都采取上一题的策略，每一次循环都穷举遍历，这样的时间复杂度达到 O ( q n ) O(qn) O(qn),对于两者都 1 0 5 10^5 105的级别来说，肯定是会超时的。我们可以考虑使用哈希表存储下每个数第一次出现的位置进行优化。

import java.util.*;
public class acwingtest{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Map map=new HashMap<>();
        for (int i = 0; i < n; i++) {
            int s=sc.nextInt();
            if (!map.containsKey(s)) map.put(s,i+1);
        }
        int q=sc.nextInt();
        while (q-->0){
            int x=sc.nextInt();
            System.out.println(map.getOrDefault(x,-1));
        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] hash=new int[100010];
        Arrays.fill(hash,-1);
        for (int i = 0; i < n; i++) {
            int s=sc.nextInt();
            if (hash[s]==-1) hash[s]=i+1;
        }
        int q=sc.nextInt();
        while (q-->0){
            int x=sc.nextInt();
            System.out.println(hash[x]);
        }
    }
}

• ( 1 ) (1) (1)HashMap是我们Java最长使用的哈希函数，它具有key和value两种属性，当我们具有key时，可以在视为 O ( 1 ) O(1) O(1)的时间复杂度内得到对应的vallue。
• ( 2 ) (2) (2)我们在接收数据时，可以预处理出每个数第一次出现的位置，containsKey函数能判断是否存在某个键，都为false时，说明当前数字是第一次出现，我们将其值为key，下标为value存入哈希函数。在查询时，getOrdefault函数能在存在该值时输出对应的value，否则输出第二个参数，也就是-1。这样总体的时间复杂度我们可以视为 O ( n ) O(n) O(n)。
• ( 3 ) (3) (3)我们也可以使用数组模拟哈希表，这样的效率会更加高效，我们以下标为key，值为value。数组模拟哈希表是我们常用的技巧。