AcWing算法基础课-789数的范围-Java题解

本篇文章分享AcWing算法基础课-789数的范围-Java题解，对你有帮助的话记得收藏一下，看Java资料网收获更多编程知识

大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》789 题——数的范围。本文详细解析了一个基于二分查找的算法题，题目要求在有序数组中查找特定元素的首次和最后一次出现的位置。通过使用两个二分查找函数，程序能够高效地处理大量查询，时间复杂度为 O(n log n)，空间复杂度为 O(n)。文章从题目描述、算法思路、具体实现步骤到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

💡算法思路

1. 使用二分查找算法findFristGreatOrEqual(int l, int r, int x)查找数组中元素 k 的开始位置
2. 如果找到了 k 的开始位置，就返回元素 k 的开始位置，并使用findFirstLessOrEqual(int l, int r, int x)查找 k 的结束位置
3. 如果没有找到 k 的开始位置，那么也不存在 k 的结束位置。直接返回-1 -1

具体实现步骤：

1. 初始化输入流：

   • 程序首先创建一个 StreamTokenizer 对象，用于从标准输入流中读取数据。这个对象通过 BufferedReader 和 InputStreamReader 来处理输入。

2. 读取数组大小和查询次数：

   • 程序调用 nextInt() 方法两次，分别读取数组的大小 n 和查询次数 q。

3. 读取数组元素：

   • 程序使用一个循环，调用 nextInt() 方法 n 次，将输入的整数依次存储到数组 nums 中。

4. 处理每个查询：

   • 程序使用一个循环，处理 q 次查询。每次查询时，程序调用 nextInt() 方法读取一个整数 k，表示要查找的值。

5. 查找首次出现的位置：

   • 程序调用 findFristGreatOrEqual(0, n - 1, k) 方法，使用二分查找算法在数组中查找第一个大于或等于 k 的元素的位置。
   • 如果找到的位置上的元素等于 k，则说明 k 存在于数组中。

6. 查找最后一次出现的位置：

   • 如果 k 存在于数组中，程序调用 findFirstLessOrEqual(0, n - 1, k) 方法，使用二分查找算法在数组中查找第一个小于或等于 k 的元素的位置。
   • 这个位置即为 k 在数组中最后一次出现的位置。

7. 输出结果：

   • 如果 k 存在于数组中，程序输出 k 的首次和最后一次出现的位置。
   • 如果 k 不存在于数组中，程序输出 -1 -1。

8. 二分查找函数的实现：

   •   findFristGreatOrEqual(int l, int r, int x)
     

     • 这个函数使用二分查找算法，在数组的 [l, r] 范围内查找第一个大于或等于 x 的元素的位置。
     • 通过不断缩小查找范围，最终找到目标位置。

   •   findFirstLessOrEqual(int l, int r, int x)
     

     • 这个函数使用二分查找算法，在数组的 [l, r] 范围内查找第一个小于或等于 x 的元素的位置。
     • 通过不断缩小查找范围，最终找到目标位置。

时间复杂度：O(n log n)
空间复杂度：O(n)

✅Java代码

import java.*;

public class Aw789 {

	// 创建一个StreamTokenizer对象，用于读取输入流
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

	// 读取下一个整数
	static int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}

	static int n, q, k;
	// 定义一个数组来存储输入的数字，数组大小为100010
	static int[] nums = new int[100000 + 10];

	public static void main(String[] args) throws IOException {
		// 读取数组的大小n和查询次数q
		n = nextInt();
		q = nextInt();
		// 读取n个整数并存储到数组nums中
		for (int i = 0; i < n; i++) {
			nums[i] = nextInt();
		}
		// 处理q次查询
		while (q-- > 0) {
			// 读取查询的数字k
			k = nextInt();
			// 查找第一个大于或等于k的元素的位置
			int left = findFristGreatOrEqual(0, n - 1, k);
			// 如果找到的元素等于k
			if (nums[left] == k) {
				// 输出第一个等于k的元素的位置和最后一个等于k的元素的位置
				System.out.println(left + " " + findFirstLessOrEqual(0, n - 1, k));
			} else {
				// 如果没有找到等于k的元素，输出-1 -1
				System.out.println("-1 -1");
			}
		}
	}

	// 二分查找第一个大于或等于x的元素的位置
	static int findFristGreatOrEqual(int l, int r, int x) {
		while (l < r) {
			int mid = l + r >> 1; // 计算中间位置
			if (nums[mid] >= x) {
				r = mid; // 如果中间元素大于或等于x，缩小右边界
			} else {
				l = mid + 1; // 否则，缩小左边界
			}
		}
		return l; // 返回找到的位置
	}

	// 二分查找第一个小于或等于x的元素的位置
	static int findFirstLessOrEqual(int l, int r, int x) {
		while (l < r) {
			int mid = (l + r + 1) >> 1; // 计算中间位置
			if (nums[mid] <= x) {
				l = mid; // 如果中间元素小于或等于x，缩小左边界
			} else {
				r = mid - 1; // 否则，缩小右边界
			}
		}
		return l; // 返回找到的位置
	}

}

🔗参考

• https://www.acwing.com/problem/content/791/

作者：程序员何未来-heweilai.com

---

🔍推荐阅读

1. AcWing算法基础课-788逆序对的数量-Java题解
2. AcWing算法基础课-787归并排序-Java题解
3. 博客赚钱全攻略：从新手到专家的变现之路

欢迎关注我的博客：@程序员何未来，持续为你输出有价值的技术文章~
你们的点赞👍 收藏⭐ 留言🗨️ 关注✅
是我持续创作，输出优质内容的最大动力！谢谢！

文章关键词：算法，计算机算法，算法题解，算法竞赛，Java，数据结构，AcWing算法基础课

文章来源:https://blog.csdn.net/coder_heweilai/article/details/142288825
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！