java 从数组中删除重复字符
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3398153/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Removing duplicate character from array
提问by TCM
While reading one book named Cracking the coding interviewby Gayle Laakmann, i came across this question
在阅读一本名为Cracking the coding interviewby 的书时Gayle Laakmann，我遇到了这个问题
Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.
设计一个算法并编写代码以在不使用任何额外缓冲区的情况下删除字符串中的重复字符。注意：一两个附加变量就可以了。数组的额外副本不是。
and this code :-
和这个代码：-
public static void removeDuplicates(char[] str) {
if (str == null) {
return;
}
int len = str.length;
if (len < 2) {
return;
}
int tail = 1;
for (int i = 1; i < len; ++i) {
int j;
for (j = 0; j < tail; ++j) {
if (str[i] == str[j]) {
break;
}
}
if (j == tail) {
str[tail] = str[i];
++tail;
}
}
str[tail] = 0;
}
which is supposed to remove duplicate character from the array. I don't quiet seem to understand what the algorithm is doing by replacing the same character again and again. I thought it's only me who feels that the algorithm is not working but infact when i ran this code it's giving me wrong outputs. Is this serious error in book or have i not understood the question?
它应该从数组中删除重复的字符。通过一次又一次地替换相同的字符，我似乎不太明白算法在做什么。我以为只有我觉得算法不起作用，但事实上，当我运行这段代码时，它给了我错误的输出。这是书中的严重错误还是我没有理解这个问题？
回答by YoK
Algo seems to be working but not clearing leftover characters. Changed code to following and it works: Note: Replaced:
Algo 似乎正在工作，但没有清除剩余的字符。将代码更改为以下内容并且它有效：注意：替换：
str[tail] = 0;
with :
和 ：
for(; tail < len;tail++){
str[tail] = 0;
}
public static void removeDuplicates(char[] str) {
if (str == null) {
return;
}
int len = str.length;
if (len < 2) {
return;
}
int tail = 1;
for (int i = 1; i < len; ++i) {
int j;
for (j = 0; j < tail; ++j) {
if (str[i] == str[j]) {
break;
}
}
if (j == tail) {
str[tail] = str[i];
++tail;
}
}
for(; tail < len;tail++){
str[tail] = 0;
}
}
回答by Thiago
A solution using a bit-vector.
使用位向量的解决方案。
Time: O(n), where n = length of the string
时间：O(n)，其中 n = length of the string
Space: O(1)
空间：O(1)
void removeduplicatas(char str[]){
int i, checker = 0, bitvalue = 0, value = 0, tail = 0;
i = 0;
tail = 0;
while(str[i]){
value = str[i] - 'a';
bitvalue = 1 << value;
if((checker & bitvalue) == 0 ){
str[tail++] = str[i];
checker |= bitvalue;
}
i++;
}
str[tail] = '#include <cstdint>
#include <iostream>
bool CheckUniqueChars(char *string, uint32_t index, uint32_t checker){
char character = string[index];
if(character=='public static void removeDuplicates(StringBuffer str) {
int len = str.length();
// if the string as less than 2 char then it can't have duplicates.
if (len < 2) {
return;
}
// fist character will never be duplicate.
// tail is the index of the next unique character.
int tail = 1;
// iterate from 2nd character.
for (int i = 1; i < len; ++i) {
int j;
// is char at index i already in my list of uniq char?
for (j = 0; j < tail; ++j) {
if (str.charAt(i) == str.charAt(j)) {
break;
}
}
// if no then add it to my uniq char list.
if (j == tail) {
str.setCharAt(tail, str.charAt(i));
// increment tail as we just added a new ele.
++tail;
}
}
// at this point the characters from index [0,tail) are unique
// if there were any duplicates they are between [tail,input.length)
// so truncate the length of input to tail.
str.setLength(tail);
}
'){
return true;
}else{
int value = character - 'a';
if((checker&(1<<value))>0){
return false;
}else{
checker |= (1<<value);
return CheckUniqueChars(string,++index,checker);
}
}
}
int main(int argc, char *argv[]){
char *string = argv[1];
uint32_t idx=0,checker=0;
if(CheckUniqueChars(string,idx,checker)){
std::cout << "all characters are unique" << std::endl;
}else{
std::cout << "there are duplicate characters" << std::endl;
}
return 0;
}
';
}
回答by Ethan Lim
This is one solution using C++ and recursion to loop through each character of the string and using the above method of bitstring in a fixed width char. You need to make sure that the fixed wide string is longer than the necessary k type characters to check.
这是使用 C++ 和递归循环遍历字符串的每个字符并在固定宽度的字符中使用上述 bitstring 方法的一种解决方案。您需要确保固定宽字符串比需要检查的 k 类型字符长。
for(; tail < len;tail++){
str[tail] = 0;
}
回答by codaddict
In Java arrays are of fixed size. So the called function cannot change the size of the input array if it finds any duplicates. Your function is just making the start index of the sub-array which has duplicates to 0. So when you print the array contents in the calling function the element which has been made 0does not get printed but elements following it (if any) do get printed.
在 Java 中，数组的大小是固定的。因此，如果发现任何重复项，被调用函数将无法更改输入数组的大小。您的函数只是将重复的子数组的起始索引设为0. 因此，当您在调用函数中打印数组内容时，0不会打印已创建的元素，但会打印其后的元素（如果有）。
The answer by YoK makes all the elements of the sub-array that are duplicates to 0. So that when you print it in the calling function the duplicates don't get printed. But you need to remember that the size of the array is still unchanged.
YoK 的答案使子数组中所有重复的元素都为 0。这样，当您在调用函数中打印它时，不会打印重复项。但是你需要记住，数组的大小仍然没有改变。
Alternatively you can return the size of the sub-array which has unique characters. Which in your case is tail.
或者，您可以返回具有唯一字符的子数组的大小。在你的情况下是tail.
One more alternative is to pass the input as a StringBufferand make the changes in-place as:
另一种选择是将输入作为 a 传递StringBuffer并进行就地更改：
public static void removeDuplicates(char[] str){
if (str == null) {
return;
}
int len = str.length;
if (len < 2) {
return;
}
int tail = 1;
for(int i=1;i<len;++i){
int j;
for(j=0;j<tail;++j){
if(str[i] == str[j]) break;
}
if(j==tail){
str[tail] = str[i];
if(i!=tail)str[i]=0;
++tail;
}else{
str[i]=0;
}
}
}
回答by Sangan K
I improvised code given by YoK to avoid using
我即兴编写了 YoK 给出的代码以避免使用
##代码##Instead we can set blank in first loop itself.
相反，我们可以在第一个循环本身中设置为空白。
##代码##