编写代码，无需使用任何额外缓冲区即可删除字符串中的重复字符。注意：一个或两个额外变量是可以的，但不能使用额外的数组。
import java.util.*;
public class Main{
public static char[] removeDupes(char[] arr){
if (arr == null || arr.length < 2)
return arr;
int len = arr.length;
int tail = 1;
for(int x = 1; x < len; x++){
int y;
for(y = 0; y < tail; y++){
if (arr[x] == arr[y]) break;
}
if (y == tail){
arr[tail] = arr[x];
tail++;
}
}
return Arrays.copyOfRange(arr, 0, tail);
}
public static char[] bigArr(int len){
char[] arr = new char[len];
Random r = new Random();
String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()-=_+[]{}|;:',.<>/?`~";
for(int x = 0; x < len; x++){
arr[x] = alphabet.charAt(r.nextInt(alphabet.length()));
}
return arr;
}
public static void main(String args[]){
String result = new String(removeDupes(new char[]{'a', 'b', 'c', 'd', 'a'}));
assert "abcd".equals(result) : "abcda should return abcd but it returns: " + result;
result = new String(removeDupes(new char[]{'a', 'a', 'a', 'a'}));
assert "a".equals(result) : "aaaa should return a but it returns: " + result;
result = new String(removeDupes(new char[]{'a', 'b', 'c', 'a'}));
assert "abc".equals(result) : "abca should return abc but it returns: " + result;
result = new String(removeDupes(new char[]{'a', 'a', 'b', 'b'}));
assert "ab".equals(result) : "aabb should return ab but it returns: " + result;
result = new String(removeDupes(new char[]{'a'}));
assert "a".equals(result) : "a should return a but it returns: " + result;
result = new String(removeDupes(new char[]{'a', 'b', 'b', 'a'}));
assert "ab".equals(result) : "abba should return ab but it returns: " + result;
char[] arr = bigArr(5000000);
long startTime = System.nanoTime();
System.out.println("2: " + new String(removeDupes(arr)));
long endTime = System.nanoTime();
long duration = (endTime - startTime);
System.out.println("Program took: " + duration + " nanoseconds");
System.out.println("Program took: " + duration/1000000000 + " seconds");
}
}
如何阅读和讨论上述代码：
- 方法 removeDupes 接受一个名为 arr 的原始字符数组。
- arr 以“按值”方式作为原始字符数组返回。传入的 arr 在主成员方法 removeDupes 结束时被垃圾回收。
- 此算法的运行时复杂度为 O(n)，更具体地说是 O(n+(small constant))，其中常数是原始字符数组中唯一字符的数量。
- copyOfRange 不会显著增加运行时复杂度，因为它只复制了少量常数项。名为 arr 的字符数组没有完全遍历。
- 如果将 null 传递给 removeDupes，则该方法返回 null。
- 如果传递空的原始字符数组或包含一个值的数组，则返回未修改的数组。
- 方法 removeDupes 的速度尽可能快，充分利用 L1 和 L2 缓存，因此 Branch redirects are kept to a minimum。
- 2015 年发布的标准计算机应该能够在包含 5 亿个字符的原始字符数组中完成此方法，时间介于 15 到 25 秒之间。
解释这段代码的工作原理：
传入数组的第一部分被用作最终返回的唯一字符的存储库。在函数开始时，答案是：“0到1之间的字符”，即0到tail之间的字符。
我们在循环外定义变量y，因为我们想要找到数组索引第一次重复出现在我们的存储库中的位置。当找到重复项时，它会跳出并退出，y==tail返回false，并且不会将其添加到存储库中。
当我们正在查看的索引x在我们的存储库中没有表示时，我们将其提取并添加到尾部的存储库中，并增加尾部的值。
最后，我们返回0和tail之间的数组，长度应该小于或等于原始数组的长度。
程序员面试谈话题：
如果将y++更改为++y，程序会有不同的行为吗？为什么？
结尾的数组复制是否代表另一个“N”通过整个数组进行使运行时复杂度变为O(n*n)而不是O(n)? 为什么？
你能用.equals方法替换原始字符的双等号比较吗？为什么或者为什么不行？
这个方法是否可以更改，以便进行“按引用”而不是现在的“按值”替换？为什么或者为什么不行？
你能通过在“arr”的开头对唯一值存储库进行排序来增加此算法的效率吗？在哪种情况下会更有效？
