Java是一種高度可靠的編程語言,具有廣泛應用的能力。其中,區間交集和并集是編程中常用的操作,下面就介紹Java中的區間交集和并集寫法。
區間交集:
public static ListintervalIntersection(List A, List B) { int i = 0, j = 0; List res = new ArrayList<>(); while (i< A.size() && j< B.size()) { int startMax = Math.max(A.get(i).start, B.get(j).start); int endMin = Math.min(A.get(i).end, B.get(j).end); if (startMax<= endMin) { res.add(new Interval(startMax, endMin)); } if (A.get(i).end< B.get(j).end) { i++; } else { j++; } } return res; }
上面的代碼中,先分別從兩個區間列表中取得一個區間A和區間B。然后將A和B的起始點的最大值和終止點的最小值算出,判斷交集是否非空。如果非空,就將該交集加入結果集中。如果A區間的終止點小于B區間的終止點,那么將A區間的下一個區間與B區間繼續比較;否則將B區間的下一個區間與A區間比較。
區間并集:
public static Listmerge(List intervals) { Collections.sort(intervals, (a, b) ->a.start - b.start); List res = new ArrayList<>(); for (Interval interval : intervals) { if (res.size() == 0 || res.get(res.size() - 1).end< interval.start) { res.add(interval); } else { res.get(res.size() - 1).end = Math.max(res.get(res.size() - 1).end, interval.end); } } return res; }
上面的代碼中,先對區間集合進行排序,以區間起始點為關鍵詞排序。然后遍歷集合中的所有區間,如果結果集合為空或者結果集合中的最后一個區間與當前區間無交集(即當前區間的起始點大于結果集中的最后一個區間的終止點),則將該區間加入結果集中;否則更新結果集合中的最后一個區間的終止點為當前區間的終止點和該區間終止點的最大值。