您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 程式設計入門

Java 字符統計與去重反序：位圖數組 O(n) 實戰與字符集查找優化

編輯：Java 程式設計入門

字符統計、去重、反序是面試高頻題，也是工具類開發常見需求。本文提供基於位圖數組的 O(n) 時間、O(1) 空間最優解法，並延伸到字符集包含關係判斷的工程化優化。

核心算法：位圖數組 + 單次遍歷

public class CharStats {
    public static void statAndReverseUnique(String input) {
        // 1. 預處理：移除空格
        String s = input.replaceAll("\\s+", "");
        char[] chars = s.toCharArray();
        
        // 2. 位圖數組：ASCII 0-255 足夠覆蓋常用字符
        int[] bitmap = new int[256];
        List uniqueReverse = new ArrayList<>();
        
        // 3. 反序遍歷 + 統計 + 去重（單次循環）
        for (int i = chars.length - 1; i >= 0; i--) {
            char c = chars[i];
            if (bitmap[c] == 0) {          // 首次遇見（反序視角）
                uniqueReverse.add(c);      // 記錄去重後的反序字符
            }
            bitmap[c]++;                   // 統計頻次
        }
        
        // 4. 輸出結果
        System.out.println("去重反序字符：" + uniqueReverse);
        for (char c : uniqueReverse) {
            System.out.printf("%c : %d 次%n", c, bitmap[c]);
        }
    }
    
    public static void main(String[] args) {
        statAndReverseUnique("A B C D E B C");
        // 輸出：
        // 去重反序字符：[C, B, E, D, A]
        // C : 2 次
        // B : 2 次
        // E : 1 次
        // D : 1 次
        // A : 1 次
    }
}

複雜度：時間 O(n)，空間 O(1)（固定 256 int 數組）。

進階：字符集包含關係判斷（面試真題優化）

問題：判斷字符串 a 中是否有字符出現在字符串 b 中，要求最高效率。

public class CharSetCheck {
    /** 位圖法：O(m+n) 時間，O(1) 空間 */
    public static boolean containsAny(String a, String b) {
        if (a == null || b == null) return false;
        boolean[] bitmap = new boolean[256]; // 或 int[256]
        for (char c : b.toCharArray()) bitmap[c] = true;
        for (char c : a.toCharArray()) if (bitmap[c]) return true;
        return false;
    }
    
    /** Java 8 Stream 寫法（可讀性優先，性能稍弱） */
    public static boolean containsAnyStream(String a, String b) {
        return a.chars().anyMatch(ch -> b.indexOf(ch) >= 0);
    }
    
    public static void main(String[] args) {
        String a = "abcd,efg";
        String b = ")(*&^%$#@![]{},.///;:'? <>";
        System.out.println(containsAny(a, b)); // true (',' 在 b 中)
    }
}

工程化封裝：通用字符統計工具類

public final class CharUtils {
    private CharUtils() {}
    
    /** 返回字符 -> 頻次映射（LinkedHashMap 保持插入序） */
    public static Map frequency(String s) {
        return s.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(
                    c -> c, LinkedHashMap::new, Collectors.counting()));
    }
    
    /** 去重反序字符列表 */
    public static List uniqueReverse(String s) {
        boolean[] seen = new boolean[256];
        List res = new ArrayList<>();
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (!seen[c]) {
                seen[c] = true;
                res.add(c);
            }
        }
        return res;
    }
    
    /** 判斷 a 是否包含 b 中任意字符 */
    public static boolean intersects(String a, String b) {
        boolean[] set = new boolean[256];
        for (char c : b.toCharArray()) set[c] = true;
        for (char c : a.toCharArray()) if (set[c]) return true;
        return false;
    }
}

Unicode 字符擴展（補充）

若需支持完整 Unicode（BMP 65536 碼位），將數組擴至 new int[65536] 或改用 Int2IntOpenHashMap（Eclipse Collections）/ long[] 位圖。對於 Emoji（增補平面），需用 codePointAt 處理代碼點而非 char。