假设给定一组N个区间（表示为左坐标和右坐标）和M个点对于每个点，p算法应该找到p所属的区间数。
我的算法是：
1）将区间的左坐标和右坐标分别放在“左”和“右”数组中
2）排序“左”，同时与“右”交换条目
3）给定一个点p，求最大i，使左[i] 4）对于每个j=p，则结果加1
5）返回结果
Java实现：
import java.util.*;
class Intervals {
public static int count(int[] left, int[] right, int point) {
int k = find(left, point), result = 0;
for (int i=0; i < k; i++)
if (point <= right[i]) result++;
return result;
}
private static int find(int[] a, int point) {
if (point < a[0]) return -1;
int i = 0;
while (i < a.length && a[i] <= point) i++;
return i;
}
private static void sort(int[] a, int[] b) {
sort(a, b, 0, a.length-1);
}
private static void sort(int[] left, int[] right, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
exchange(left, right, lo, lo + (int) (Math.random() * (hi-lo+1)));
int v = left[lo];
int i = lo;
while (i <= gt) {
if (left[i] < v) exchange(left, right, lt++, i++);
else if (left[i] > v) exchange(left, right, i, gt--);
else i++;
}
sort(left, right, lo, lt-1);
sort(left, right, gt+1, hi);
}
private static void exchange(int[] left, int[] right, int i, int j) {
int temp = left[i];
left[i] = left[j];
left[j] = temp;
temp = right[i];
right[i] = right[j];
right[j] = temp;
}
private static boolean less(int[] a, int i, int j) {
return a[i] < a[j];
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int m = Integer.parseInt(args[1]);
int[] left = new int[n];
int[] right = new int[n];
Random r = new Random();
int MAX = 100000;
for (int i = 0; i < n; i++) {
left[i] = r.nextInt(MAX);
right[i] = left[i] + r.nextInt(MAX/4);
}
sort(left, right);
for (int i=0; i < m; i++)
System.out.println(count(left, right, r.nextInt(MAX)));
}
}
这段代码还没有通过测试，我正试图找到一个bug。关键是我实际上不知道这些测试中使用了什么输入数据。
谢谢。
最佳答案
可能不是你想要的答案，但可能是某一天有人遇到这个问题的答案。
如果您计划经常查询一组相当静态的范围，那么您可能希望考虑使用Interval Tree。
public class IntervalTree<T extends IntervalTree.Interval> {
// My intervals.
private final List<T> intervals;
// My center value. All my intervals contain this center.
private final long center;
// My interval range.
private final long lBound;
private final long uBound;
// My left tree. All intervals that end below my center.
private final IntervalTree<T> left;
// My right tree. All intervals that start above my center.
private final IntervalTree<T> right;
public IntervalTree(List<T> intervals) {
if (intervals == null) {
throw new NullPointerException();
}
// Initially, my root contains all intervals.
this.intervals = intervals;
// Find my center.
center = findCenter();
/*
* Builds lefts out of all intervals that end below my center.
* Builds rights out of all intervals that start above my center.
* What remains contains all the intervals that contain my center.
*/
// Lefts contains all intervals that end below my center point.
final List<T> lefts = new ArrayList<T>();
// Rights contains all intervals that start above my center point.
final List<T> rights = new ArrayList<T>();
long uB = Long.MIN_VALUE;
long lB = Long.MAX_VALUE;
for (T i : intervals) {
long start = i.getStart();
long end = i.getEnd();
if (end < center) {
lefts.add(i);
} else if (start > center) {
rights.add(i);
} else {
// One of mine.
lB = Math.min(lB, start);
uB = Math.max(uB, end);
}
}
// Remove all those not mine.
intervals.removeAll(lefts);
intervals.removeAll(rights);
uBound = uB;
lBound = lB;
// Build the subtrees.
left = lefts.size() > 0 ? new IntervalTree<T>(lefts) : null;
right = rights.size() > 0 ? new IntervalTree<T>(rights) : null;
// Build my ascending and descending arrays.
/**
* @todo Build my ascending and descending arrays.
*/
}
/*
* Returns a list of all intervals containing the point.
*/
List<T> query(long point) {
// Check my range.
if (point >= lBound) {
if (point <= uBound) {
// In my range but remember, there may also be contributors from left or right.
List<T> found = new ArrayList<T>();
// Gather all intersecting ones.
// Could be made faster (perhaps) by holding two sorted lists by start and end.
for (T i : intervals) {
if (i.getStart() <= point && point <= i.getEnd()) {
found.add(i);
}
}
// Gather others.
if (point < center && left != null) {
found.addAll(left.query(point));
}
if (point > center && right != null) {
found.addAll(right.query(point));
}
return found;
} else {
// To right.
return right != null ? right.query(point) : Collections.<T>emptyList();
}
} else {
// To left.
return left != null ? left.query(point) : Collections.<T>emptyList();
}
}
private long findCenter() {
//return average();
return median();
}
/**
* @deprecated Causes obscure issues.
* @return long
*/
@Deprecated
protected long average() {
// Can leave strange (empty) nodes because the average could be in a gap but much quicker.
// Don't use.
long value = 0;
for (T i : intervals) {
value += i.getStart();
value += i.getEnd();
}
return intervals.size() > 0 ? value / (intervals.size() * 2) : 0;
}
protected long median() {
// Choose the median of all centers. Could choose just ends etc or anything.
long[] points = new long[intervals.size()];
int x = 0;
for (T i : intervals) {
// Take the mid point.
points[x++] = (i.getStart() + i.getEnd()) / 2;
}
Arrays.sort(points);
return points[points.length / 2];
}
void dump() {
dump(0);
}
private void dump(int level) {
LogFile log = LogFile.getLog();
if (left != null) {
left.dump(level + 1);
}
String indent = "|" + StringUtils.spaces(level);
log.finer(indent + "Bounds:- {" + lBound + "," + uBound + "}");
for (int i = 0; i < intervals.size(); i++) {
log.finer(indent + "- " + intervals.get(i));
}
if (right != null) {
right.dump(level + 1);
}
}
/*
* What an interval looks like.
*/
public interface Interval {
public long getStart();
public long getEnd();
}
/*
* A simple implemementation of an interval.
*/
public static class SimpleInterval implements Interval {
private final long start;
private final long end;
public SimpleInterval(long start, long end) {
this.start = start;
this.end = end;
}
public long getStart() {
return start;
}
public long getEnd() {
return end;
}
@Override
public String toString() {
return "{" + start + "," + end + "}";
}
}
/**
* Not called by App, so you will have to call this directly.
*
* @param args
*/
public static void main(String[] args) {
/**
* @todo Needs MUCH more rigorous testing.
*/
// Test data.
long[][] data = {
{1, 2},
{2, 9},
{4, 8},
{3, 5},
{7, 9},};
List<Interval> intervals = new ArrayList<Interval>();
for (long[] pair : data) {
intervals.add(new SimpleInterval(pair[0], pair[1]));
}
// Build it.
IntervalTree<Interval> test = new IntervalTree<Interval>(intervals);
// Test it.
System.out.println("Normal test: ---");
for (long i = 0; i < 10; i++) {
List<Interval> intersects = test.query(i);
System.out.println("Point " + i + " intersects:");
for (Interval t : intersects) {
System.out.println(t.toString());
}
}
// Check for empty list.
intervals.clear();
test = new IntervalTree<Interval>(intervals);
// Test it.
System.out.println("Empty test: ---");
for (long i = 0; i < 10; i++) {
List<Interval> intersects = test.query(i);
System.out.println("Point " + i + " intersects:");
for (Interval t : intersects) {
System.out.println(t.toString());
}
}
}
}
关于java - 给定一组间隔，找出包含一个点的间隔，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23062568/