Java 求数的范围

时间:2022-01-17作者:klpeng分类:IT综合浏览:124评论:0

题目:

给定一个按照升序排列的长度为 nn 的整数数组,以及 qq 个查询。

对于每个查询,返回一个元素 kk 的起始位置和终止位置(位置从 00 开始计数)。

如果数组中不存在该元素,则返回 -1 -1

输入格式

第一行包含整数 nn 和 qq,表示数组长度和询问个数。

第二行包含 nn 个整数(均在 1∼100001∼10000 范围内),表示完整数组。

接下来 qq 行,每行包含一个整数 kk,表示一个询问元素。

输出格式

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

如果数组中不存在该元素,则返回 -1 -1

数据范围

1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000

输入样例:

6 3
1 2 2 3 3 4
3
4
5

输出样例:

3 4
5 5
-1 -1

题解:

         我们发现如果数组内存在查找的数,那么数的起始位置一定是数组从左往右找到这个数的第一个下标,数的终止位置一定是从右往左找到的第一个下标。

代码:

import java.util.*;

public class Main{
    
    
    public static void main(String[]args){
        Scanner sc= new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int nums [] = new int[n];
        for(int i =0 ;i<n;i++){
            nums[i]= sc.nextInt();
        }
        for(int j = 0 ; j< m ;j++){
            int temp = sc.nextInt();
            int l = -1;   //初始化为-1
            int r = -1;
            for(int i = 0 ;i<n;i++){  //从左往右开始找第一个
                if(nums[i] == temp){
                    l = i;
                    break;
                }
            }
            for(int k = n-1 ;k>=0;k--){ 从右往左开始找第一个
                if(nums[k] == temp){
                    r = k ;
                    break;
                }
            }
            System.out.println(l+" "+r);
        }
        
        
        
        
    }
    
    
}

       

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢