本文主要是介绍205.Interval Minimum Number-区间最小数(中等题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
区间最小数
题目
给定一个整数数组(下标由 0 到 n-1,其中 n 表示数组的规模),以及一个查询列表。每一个查询列表有两个整数 [start, end]。 对于每个查询,计算出数组中从下标 start 到 end 之间的数的最小值,并返回在结果列表中。
注意事项
在做此题前,建议先完成以下三道题 线段树的构造, 线段树的查询 及 线段树的修改。样例
对于数组 [1,2,7,8,5], 查询 [(1,2),(0,4),(2,4)],返回 [2,1,5]
挑战
每次查询在O(logN)的时间内完成
题解
构建线段树,逐个进行查找。
/*** Definition of Interval:* public classs Interval {* int start, end;* Interval(int start, int end) {* this.start = start;* this.end = end;* }*/class SegmentTreeNode {public int start, end, min;public SegmentTreeNode left, right;public SegmentTreeNode(int start, int end, int min) {this.start = start;this.end = end;this.min = min;this.left = this.right = null;}
}public class Solution {/***@param A, queries: Given an integer array and an query list*@return: The result list*/public ArrayList<Integer> intervalMinNumber(int[] A, ArrayList<Interval> queries) {ArrayList<Integer> result = new ArrayList<Integer>();SegmentTreeNode root = new SegmentTreeNode(0,A.length-1,0);create(A,root);//生成线段树for (int i=0;i<queries.size();i++){Interval interval = queries.get(i);result.add(query(root,interval.start,interval.end));}return result;}private void create(int[] A, SegmentTreeNode root){if (root.start == root.end){root.min = A[root.start];return;}int mid = (root.start + root.end) / 2;root.left = new SegmentTreeNode(root.start,mid,0);root.right = new SegmentTreeNode(mid+1,root.end,0);create(A,root.left);create(A,root.right);root.min = Math.min(root.left.min,root.right.min);}//查询最小数private int query(SegmentTreeNode root, int start, int end){if (root.start == start && root.end == end){return root.min;}int leftMin = Integer.MAX_VALUE;int rightMin = Integer.MAX_VALUE;int mid = (root.start + root.end) / 2;if (mid >= start){leftMin = query(root.left,start,Math.min(mid,end));}if (mid < end){rightMin = query(root.right,mid>=start?mid+1:start,end);}return Math.min(leftMin,rightMin);}
}
Last Update 2016.11.4
这篇关于205.Interval Minimum Number-区间最小数(中等题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!