0

配列を取得し、重複がないかどうかを確認し、その文字のすべてのインスタンスを削除しようとしています。現在使用しようとしている方法は非常に醜いです。

例;

In: ABBCCDE
Out: ADE

または

In: BCACDF
Out: BADF

現在、2つの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

この問題には非常に多くの解決策があり、入力に応じて最適な解決策は異なります。

ロメディウスが彼の答えで提案した解決策は、マコトの答えに対する彼のコメントでアレックスが提案したものと同じように良いものです。

HashSet / HashMapがO（1）である操作を持っていると考える場合、それらはO（n）です。ただし、現実にはこれはめったにないことであり、ハッシュ関数の適切性とリンクリストの配列のサイズ変更（または内部で使用される構造-JavaはデフォルトでLLを使用）によって異なります。

したがって、たとえば、JavaのHashMapsとHashSetsには、最悪の場合にO（n）が挿入されます。これは、重複を検証して、単にテールに追加するのではなく、リンクリストを反復処理するためです。これは、衝突の数が多い場合にのみ発生します。

入力のサイズがわかっている場合は、HashSet / HashMapのサイズを設定することをお勧めします。HashMap（intinitialCapacity）コンストラクターがこれを行います。これにより、パフォーマンスに大きな影響を与える可能性のある構造のサイズ変更の問題を防ぐことができます。

そうしないと、デフォルトの容量が使用されます。次に、ハッシュ関数がどれだけ優れているかにのみ依存します。

O（n log n）である信頼できる解決策は、入力を並べ替えてから、配列の前後の位置が選択した位置と等しいかどうかを1回だけ繰り返し、ある場合は追加しないことです。この2番目の部分はO（n）です。ソートはO（n logn）であることが保証されており、Java 7を使用している場合は、非常に高速なtimsortが使用されます。

私が誰かにインタビューしているなら、私はどちらの解決策も受け入れます。

于 2012-10-04T04:04:29.410 に答える
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は保持しないため、HashMultisetではなくLinkedHashMultisetを使用することが重要です。

また、一時的なコレクションが多数作成されるため、これが最もメモリ効率の高いソリューションであるとは言えません。

ただし、コードの観点からは単純であり、誰かがコードを見るだけで、あなたが何をしようとしているのかを推測することができます。

于 2012-10-04T04:17:32.503 に答える
1

あなたはエレガントを定義していませんが、私はビットマスクとXORを使用して重複を削除して提出します。これは、重複を削除するためのナビゲートセットを不要にするため、エレガントで非常に効率的であると私は主張します。

（これは大文字に対してのみ機能しますが、拡張するのは簡単です。）

これは、アイデアの鍵となるクラスです。これはビットセットの単純なラッパーであり、現在の文字、またはどの文字が表示されたかなどを示すために使用されます。

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

を使用SETすると、重複する値を自動的に削除できます。配列を使用しているため、を使用して変換する必要がありますArrays.asList(T.. a)

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

  • に基づくソリューションは、Javaでの変換とその逆Setの変換がサポートされていないため、洗練されていません。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 に答える