Это - это , что позволяет эффективно сделать это на месте. Вам нужно будет перезаписывать символы в буфере через определенные промежутки времени, а затем логически сокращать буфер с помощью setLength. Это будет довольно сложно, но это будет на месте и O(N).
Причина, по которой вы хотите перезаписать вместо использования delete / insert, заключается в том, что вместо этого будет O(N^2), потому что вещи нужно перемещать без необходимости.
Выполнение этого неуместно довольно тривиально и O(N), но потребует вторичного буфера, удваивающего пространство.
проверка концепции
Вот простое доказательство концепции. removeIntervals занимает StringBuffer и int[][] intervals. Предполагается, что каждый int[] является парой значений { start, end } (полуоткрытый диапазон, исключительная верхняя граница). В линейном времени и на месте эти интервалы удаляются из StringBuffer простым overwrite. Это работает, когда интервалы отсортированы и не перекрываются и обрабатываются слева направо.
Затем буфер укорачивается на setLength, обрезая столько символов, которые были удалены.
static void overwrite(StringBuffer sb, int dst, int srcFrom, int srcTo) {
for (int i = srcFrom; i < srcTo; i++) {
sb.setCharAt(dst++, sb.charAt(i));
}
}
static int safeGet(int[][] arr, int index, int defaultValue) {
return (index < arr.length) ? arr[index][0] : defaultValue;
}
static void removeIntervals(StringBuffer sb, int[][] intervals) {
int dst = safeGet(intervals, 0, 0);
int removed = 0;
for (int i = 0; i < intervals.length; i++) {
int start = intervals[i][0];
int end = intervals[i][1];
int nextStart = safeGet(intervals, i+1, sb.length());
overwrite(sb, dst, end, nextStart);
removed += end - start;
dst += nextStart - end;
}
sb.setLength(sb.length() - removed);
}
Тогда мы можем проверить это следующим образом:
String text = "01234567890123456789";
int[][][] tests = {
{ { 0, 5, },
}, // simple test, removing prefix
{ { 1, 2, }, { 3, 4, }, { 5, 6, }
}, // multiple infix removals
{ { 3, 7, }, { 18, 20, },
}, // suffix removal
{
}, // no-op
{ { 0, 20 },
}, // remove whole thing
{ { 7, 10 }, { 10, 13 }, {15, 15 },
}, // adjacent intervals, empty intervals
};
for (int[][] test : tests) {
StringBuffer sb = new StringBuffer(text);
System.out.printf("> '%s'%n", sb);
System.out.printf("- %s%n", java.util.Arrays.deepToString(test));
removeIntervals(sb, test);
System.out.printf("= '%s'%n%n", sb);
}
Это печатает ( как видно на ideone.com ):
> '01234567890123456789'
- [[0, 5]]
= '567890123456789'
> '01234567890123456789'
- [[1, 2], [3, 4], [5, 6]]
= '02467890123456789'
> '01234567890123456789'
- [[3, 7], [18, 20]]
= '01278901234567'
> '01234567890123456789'
- []
= '01234567890123456789'
> '01234567890123456789'
- [[0, 20]]
= ''
> '01234567890123456789'
- [[7, 10], [10, 13], [15, 15]]
= '01234563456789'
Получение интервалов
В этом конкретном случае интервалы могут быть либо построены за предварительный проход (с использованием indexOf), либо весь процесс может быть выполнен за один проход, если это абсолютно необходимо. Дело в том, что это определенно можно сделать на месте за линейное время (и, если это абсолютно необходимо, за один проход).
Неуместное решение
Это неуместно с использованием вторичного буфера и регулярных выражений. Он предлагается к рассмотрению из-за своей простоты. Если дальнейшая оптимизация не требуется доказуемо (после результатов доказательного профилирования), этого должно быть достаточно:
String text =
"DEL: line1\n" +
"KEP: line2\r\n" +
"DEL: line3\n" +
"KEP: line4\r" +
"DEL: line5\r" +
"DEL: line6\r" +
"KEP: line7\n" +
"DEL: line8";
StringBuffer sb = new StringBuffer(text);
Pattern delLine = Pattern.compile("(?m)^DEL:.*$");
String cleanedUp = delLine.matcher(sb).replaceAll("<deleted!>");
System.out.println(cleanedUp);
Это печатает ( как видно на ideone.com ):
<deleted!>
KEP: line2
<deleted!>
KEP: line4
<deleted!>
<deleted!>
KEP: line7
<deleted!>
Ссылки