题解：AcWing 789. 数的范围 JAVA-阿里云开发者社区

题解：AcWing 789. 数的范围 JAVA

2022-01-17 136

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 题解：AcWing 789. 数的范围 JAVA

题目描述

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。

数据范围

1≤n≤100000

1≤q≤10000

1≤k≤10000

样例

输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1

优化二分查找跳过重复元素

此题采用正常的二分查找会超时，但我们可以注意到，此题有很多重复的数字例如（111223333）

我们二分查找时左边查找到第一个1的时候就可以跳过其余的1

可以通过一个数组来实现记录重复数字的个数，在二分查找时可以直接跳过

java代码

package 蓝桥;
import java.util.Scanner;
/******
 * 
 * @author genji
 * 此题采用正常的二分查找会超时，但我们可以注意到，此题有很多重复的数字例如（111223333）
 * 我们二分查找时左边查找到第一个1的时候就可以跳过其余的1
 * 可以通过一个数组来实现记录重复数字的个数，在二分查找时可以直接跳过
 */
public class 数的范围_789 {
  public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int n=scanner.nextInt(),m=scanner.nextInt();
    int[] a=new int[n];
    int[] b=new int[n];//b中存放重复数字的数量，因为下面采用二分查找所以有前后两个标志
    //例如a 中的数为1,1,1,1,1,2,2,2,2,3,3,4,4,4,4,5
    //则b中的数为      5,0,0,0,5,4,0,0,4,2,2,4,0,0,4,1
    //使其在查找时跳过重复的数字
    int c=0,i;
    for (i = 0; i < n; i++) {
      a[i]=scanner.nextInt();
      if (i==0||a[i]==a[i-1]) {
        c++;        //如果是第一个数或者和前面数字相同的数则记录相同数字的个数
      }
      else if (a[i]!=a[i-1]) {
        b[i-1]=c;
        b[i-c]=c;     //将相同数字个数赋到b数组相同下标的头和尾
        c=1;
      }
    }
    b[i-1]=c;
    b[i-c]=c;
    for (i = 0; i < b.length; i++) {
      System.out.println(b[i]);
    }
    while (m-->0) {
      int l=0,r=n-1;
      int q=scanner.nextInt();
      while (l<r) {
        if (a[l]!=q) {
          l+=b[l];//   跳过重复的数字
        }
        if (a[r]!=q) {
          r-=b[r];//   跳过重复的数字
        }
        if (a[r]==q&&a[l]==q) {
          System.out.println(l+" "+r);
          break;
        }
      }
      if(a[l]!=q&&a[r]!=q)
      {
        System.out.println(-1+" "+-1);
      }
    }
  }
}