有人在bh买过背景布么？# PhotoGear - 摄影器材
e*i
1 楼
这是我写的insert intervals的code.
想问下，这里面sort的O(n)是多少？
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
// Start typing your Java solution below
// DO NOT write main() function
if (newInterval == null) {
return intervals;
}
ArrayList result = new ArrayList();
for (Interval item:intervals) {
if (item.start > newInterval.end || item.end < newInterval.start
) {
result.add(item);
}
else{
newInterval.start = Math.min(newInterval.start, item.start);
newInterval.end = Math.max(newInterval.end, item.end);
}
}
result.add(newInterval);
Collections.sort(result, INTERVAL_COMPARATOR);
return result;
}
Comparator INTERVAL_COMPARATOR = new Comparator(){
public int compare(Interval a, Interval b){
return new Integer(a.start).compareTo(new Integer(b.start));
}
}
}
想问下，这里面sort的O(n)是多少？
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList
Interval newInterval) {
// Start typing your Java solution below
// DO NOT write main() function
if (newInterval == null) {
return intervals;
}
ArrayList
for (Interval item:intervals) {
if (item.start > newInterval.end || item.end < newInterval.start
) {
result.add(item);
}
else{
newInterval.start = Math.min(newInterval.start, item.start);
newInterval.end = Math.max(newInterval.end, item.end);
}
}
result.add(newInterval);
Collections.sort(result, INTERVAL_COMPARATOR);
return result;
}
Comparator
public int compare(Interval a, Interval b){
return new Integer(a.start).compareTo(new Integer(b.start));
}
}
}
