Инвертировать строку в Java в O (1)?
Есть ли какое-либо средство в стандартных библиотеках Java, которое, учитывая CharSequence, производит реверс в O (1) время?
Я предполагаю, что это "легко" реализовать, просто задавшись вопросом, существует ли это уже. (Я подозреваю причину, которую это не предлагается, то, потому что "легкий" путь на самом деле повредил бы мультисимвольные кодовые точки - но во многих случаях мы знаем, что не имеем дело с теми).
Спасибо
Обновите Heh, немного забавно что больше всего мысль эта "невозможная", хорошая работа парни! Ну, на самом деле это (концептуально) тривиально - pseudojava, следует для прояснения:
class MyReverseString extends String { //of course I can't extend String!
final String delegate;
MyReverseString(String delegate) { this.delegate = delegate; }
int length() { return delegate.length(); }
int charAt(int i) { return delegate.charAt(delegate.length() - 1 - i); }
}
Я еще оставляю вопрос открытым для некоторых, только в редком случае, что что-то как очевидное решение (например, видят Jon Skeet один) уже существует в JDK, и кто-то знает об этом. (Снова, очень вряд ли из-за тех противных кодовых точек).
Редактирование, Вероятно, беспорядок произошло от меня имеющий "строку" в заголовке (но не Строка!), тогда как я только прошу "реверс CharSequence". Если Вы были смущены, извините. Я надеялся бы, что O (1) часть сделает точно ясным, относительно чего просили.
И между прочим, это было вопросом, который заставил меня спросить этого. (Это - случай, где было бы легче выполнить regex справа налево, не слева направо, таким образом, может быть некоторое практическое значение даже для simple/broken-codepoints реализации),
6 ответов
Ну, вы можете легко создать реализацию CharSequence, которая возвращает ту же длину, а при запросе конкретного символа возвращает тот, который находится по адресу length-index-1. toString() становится O(n), конечно...
Создание обратного CharSequence будет O(1) - все, что нужно сделать, это сохранить ссылку на исходное CharSequence, в конце концов. Однако итерация по всем символам в последовательности будет O(n), что очевидно.
Обратите внимание, что создание обратного CharSequence (согласно телу вашего вопроса) - это не то же самое, что создание обратного String (согласно заголовку вашего вопроса). На самом деле создание String - это O(n), и так и должно быть.
Пример кода, в основном не проверенный:
public final class ReverseCharSequence implements CharSequence
{
private final CharSequence original;
public ReverseCharSequence(CharSequence original)
{
this.original = original;
}
public int length()
{
return original.length();
}
public char charAt(int index)
{
return original.charAt(original.length() - index - 1);
}
public CharSequence subSequence(int start, int end)
{
int originalEnd = original.length() - start;
int originalStart = original.length() - end;
return new ReverseCharSequence(
original.subSequence(originalStart, originalEnd));
}
public String toString()
{
return new StringBuilder(this).toString();
}
}
StringBuffer имеет реверс: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html#reverse()
BTW, я предполагаю, что вы имели в виду O(n), потому что O(1) (как упоминали другие люди) очевидно невозможно.
Это невозможно. Чтобы развернуть строку, необходимо обработать каждый символ хотя бы один раз, следовательно, это должно быть как минимум O(n).
Как уже писали все остальные, это невозможно за время O (1), так как вам нужно смотреть хотя бы на каждый символ один раз.
Но если вы имели в виду, как это сделать в пространстве O (1), вот оно: если вы хотите сделать это в пространстве O (1), вы, очевидно, не можете выделить новую строку той же длины, но у вас есть чтобы поменять местами символы на месте.
Итак, все, что вам нужно сделать, это перебрать слева до середины строки и одновременно справа налево и поменять местами элементы. Псевдокод (Условные обозначения: пусть строка s будет доступна с n -го символа через s [n] . Если s имеет длину k , мы говорим, что у него есть элементы 0 до k-1 ):
for i=0; i<len(s)/2; ++i{
char tmp = s[i]
s[i] = s[len(s)-1-i]
s[len(s)-1-i] = tmp
}
Итак, вы видите, все, что вам нужно, это вспомогательная переменная tmp , содержащий текущий символ для его замены, так что вы можете сделать это в пространстве O (1).
string result = new StringBuffer(yourString).reverse().toString();
В зависимости от того, что вы понимаете под O (1), это кажется невозможным, поскольку даже для однократного чтения строки требуется O (n), где n - количество символов в строке.
Решение Джона Скита, вероятно, наиболее эффективно. Но если вам просто нужно быстро и грязно, это должно сработать, и я не думаю, что он будет сильно отставать по производительности.
StringBuffer reverse=new StringBuffer(original.toString()).reverse();
StringBuffer - это CharSequence, поэтому, если вы подразумеваете, что результатом должно быть CharSequence, это так.
Что ж, это может быть быстрее, чем решение мистера Скита, если вы исследуете последовательность несколько раз, так как это устраняет накладные расходы на вычисления, чтобы найти правильную позицию символа каждый раз, когда вы читаете символ. Он будет делать это только один раз для каждого персонажа.
Если бы я собирался сделать миллиард из них, возможно, я бы сделал тест.