0

我正在尝试获取一个数组，检查是否有任何欺骗，并删除该字母的所有实例，我目前尝试使用的方法非常难看

例子;

In: ABBCCDE
Out: ADE

或者

In: BCACDF
Out: BADF

我目前正在使用两个for循环来查找骗子，将该骗子的 Char[] 添加到 OTHER 数组中，然后再循环使用 2 个 for 循环从我的 ErrorArray 中删除字符。

4

7 回答 7

5

这可能是一个解决方案：

public static void main(String[] args) {
    char[] arr = { 'A', 'B', 'B', 'C', 'C', 'D', 'E' };
    Set<Character> in = new HashSet<>();
    Set<Character> dupe = new HashSet<>();
    for (char c : arr) {
        if (!dupe.contains(c)) {
            if (in.contains(c)) {
                dupe.add(c);
                in.remove(c);
            } else {
                in.add(c);
            }
        }
    }
    char[] arrR = new char[in.size()];
    int i = 0;
    for (char c : in) {
        arrR[i++] = c;
    }
    for (char c : arrR) {
        System.out.println(c);
    }
}
于 2012-10-04T02:42:01.877 回答
3 
public static String removeDuplicateChars (String sText)
{
    String sResult = "";
    char[] caText = sText.toCharArray();
    int[] iaAsciiIndex = new int[128];

    for (int i=0 ; i<caText.length; i++)
    {
        iaAsciiIndex[caText[i]] += 1;
    }

    for (int i=0 ; i<iaAsciiIndex.length ; i++)
    {
        if (iaAsciiIndex[i] == 1)
            sResult += (char)i;
    }

    return sResult;
}
于 2012-11-30T14:29:48.840 回答
2

这个问题有很多解决方案，并且根据输入的不同，最佳解决方案也会有所不同。

romedius 在他的回答中提出的解决方案很好，就像 Alex 在他对 Makoto 回答的评论中提出的解决方案一样。

如果您认为 HashSet/HashMap 具有 O(1) 的操作，那么它们是 O(n)。但是，现实情况表明这种情况很少发生，这取决于您的哈希函数的适用程度和链表数组的大小调整（或内部使用的任何结构 - Java 默认使用 LL）。

因此，例如：Java 的 HashMaps 和 HashSets 的最坏情况插入 O(n)，因为它们验证重复项并因此迭代链表，而不是仅仅添加到它的尾部。这仅在碰撞次数较多时发生。

如果您知道输入的大小，最好将 HashSet/HashMap 的大小设置为它：HashMap(int initialCapacity) 构造函数执行此操作。这样可以防止调整结构的大小问题，这会严重影响性能。

如果不这样做，它将使用默认容量。然后你只取决于哈希函数有多好。

O(n log n) 的可靠解决方案是对输入进行排序，然后只需迭代一次，检查数组的前一个或后一个位置是否等于所选位置，如果有，则不要添加它。第二部分是 O(n)。排序保证为 O(n logn)，如果您使用的是 Java 7，它将使用非常快的 timsort。

如果我正在采访某人，我会接受任何一种解决方案。

于 2012-10-04T04:04:29.410 回答
1

您没有定义优雅，但我提交使用位掩码和 XOR 来删除欺骗。我认为这是优雅且非常有效的，因为它避免了导航集以删除欺骗。

（这只适用于大写字母，但很容易扩展。）

这是一个关键的想法的类。它是一个简单的 BitSet 包装器，用于表示当前字符或已看到的字符等：

class Bitmask {
    private static final int NUM_BITS = 26;
    private static final int OFFSET = 65;
    // e.g. {A,C,D} == [1,0,1,1,0, ...]
    BitSet bitset = new BitSet(NUM_BITS);

    public Bitmask() {}

    public Bitmask(Bitmask bitmask) {
        this.bitset = (BitSet) bitmask.bitset.clone();
    }
    public void set(char c) {
        int whichBit = (int) c - OFFSET;
        bitset.set(whichBit);        
    }

    public List<Character> getAllSet() {
        List<Character> all = new ArrayList<Character>();
        for (int i = 0; i < NUM_BITS; i++) {
            if (bitset.get(i)) {
                char c = (char) (OFFSET + i);
                all.add(new Character(c));
            }
        }        
        return all;
    }

    public void xor(Bitmask bitmask) {
        this.bitset.xor(bitmask.bitset);
    }

    public void or(Bitmask bitmask) {
        this.bitset.or(bitmask.bitset);
    }

    public void and(Bitmask bitmask) {
        this.bitset.and(bitmask.bitset);
    }

    public void andNot(Bitmask bitmask) {
        this.bitset.andNot(bitmask.bitset);
    }    
}

这看起来很冗长，但回报在于算法，它对N 个位集的 XOR 的这个答案欠下了一大笔债。

char[] input = {'A', 'B', 'B', 'B', 'C', 'D', 'E'};  //expect 'ACDE'
//char[] input = {'A', 'A', 'B', 'B', 'B', 'C'};
//char[] input = {'A', 'C', 'G' };

Bitmask moreThanOnceBitmask = new Bitmask();
Bitmask onceBitmask = new Bitmask();

for(char c : input) {
    Bitmask thisBitmask = new Bitmask();
    thisBitmask.set(c);
    Bitmask tmpOnceBitmask = new Bitmask(onceBitmask);
    // we've seen 'char c' at least once
    onceBitmask.or(thisBitmask);
    // we've seen 'char c' more than once
    tmpOnceBitmask.and(thisBitmask);
    moreThanOnceBitmask.or(tmpOnceBitmask);
}

// we want 'at least once' but not 'more than once'
Bitmask finalBitmask = new Bitmask(onceBitmask);
finalBitmask.andNot(moreThanOnceBitmask);

// build list

System.out.println(finalBitmask.getAllSet().toString());
于 2012-10-04T03:29:35.727 回答
1

Guava 的多集类的合理解决方案：

    char[] chars = new char[] { 'A', 'B', 'B', 'B', 'C', 'D', 'C', 'E' };

    Multiset<Character> set =  LinkedHashMultiset.create(Chars.asList(chars));

    for (char c : chars ) {
       int cnt = set.count(c);
       if (cnt > 1) {
           set.remove(c, cnt);
       }
    }

    char[] singles = Chars.toArray(set);

    System.out.println(new String(singles));

PS：使用 LinkedHashMultiset 而不是 HashMultiset 很重要，因为 LinkedHashMultiset 版本在您遍历它时会保留插入顺序，而 HashMultiset 则不会。

而且我并不认为这是最节省内存的解决方案，因为创建了很多临时集合。

但是，从代码的角度来看，它很简单，有人可以通过查看您的代码来推断您正在尝试做什么。

于 2012-10-04T04:17:32.503 回答
1

使用SET允许您自动删除任何重复值。由于您使用的是数组，因此您需要使用Arrays.asList(T.. a)

SET<Character> uniqueCharacters = new HashSet<Character>(Arrays.asList(yourArray));
于 2012-10-04T02:40:17.037 回答
0

  • Set由于 Java 缺乏对来回转换的支持，char[]基于的解决方案并不优雅Set<Character>。

  • 上述转换所需的循环更有效地用于执行问题所需的实际处理。

  • 我认为以下解决方案的极端简单性使其优雅。

  • 它也是有效的，尽管以（有点）大数组为代价，根据对所需输入字符集的了解，该数组的大小可能会减小。

    public class Test extends TestCase {

    public void testDupes() {
        assertEquals("ADE", noDupes("ABBCCDE".toCharArray()));
        assertEquals("BADF", noDupes("BCACDF".toCharArray()));
    }

    public String noDupes(char[] in) {
        int[] count = new int[Character.MAX_VALUE];
        for (char c: in)
            count[c]++;
        StringBuffer out = new StringBuffer();
        for (char c: in)
            if (count[c]==1)
                out.append(c);
        return out.toString();
    }
}
于 2012-10-04T07:49:22.723 回答