【剑指Offer】50. 第一个只出现一次的字符位置

浅浅的花香味﹌ 2022-12-01 14:13 115阅读 0赞

[NowCoder][]

## 题目描述 ##

在一个字符串中找到第一个只出现一次的字符，并返回它的位置。

Input: abacc
    Output: b

## 解题思路 ##

最直观的解法是使用 HashMap 对出现次数进行统计

import java.util.*;
    import java.lang.*;
    
    public class Solution { 
        public int FirstNotRepeatingChar(String str) { 
            HashMap<Character, Boolean> hash = new HashMap<>();
            char[] arr = str.toCharArray();
            
            for(char c : arr) 
                hash.put(c, !hash.containsKey(c)); // 插入true 重复了就变成false
    
            for(int i = 0; i < arr.length; i++)
                if(hash.get(arr[i]))
                    return i;
            
            return -1;
        }
    }

考虑到要统计的字符范围有限，因此可以使用整型数组代替 HashMap，从而将空间复杂度由 O(N) 降低为 O(1)。

public int FirstNotRepeatingChar(String str) { 
        int[] cnts = new int[256];
        for (int i = 0; i < str.length(); i++)
            cnts[str.charAt(i)]++;
        for (int i = 0; i < str.length(); i++)
            if (cnts[str.charAt(i)] == 1)
                return i;
        return -1;
    }

以上实现的空间复杂度还不是最优的。考虑到只需要找到只出现一次的字符，那么需要统计的次数信息只有 0,1,更大，使用两个比特位就能存储这些信息。

public int FirstNotRepeatingChar2(String str) { 
        BitSet bs1 = new BitSet(256);
        BitSet bs2 = new BitSet(256);
        for (char c : str.toCharArray()) { 
            if (!bs1.get(c) && !bs2.get(c))
                bs1.set(c);     // 0 0 -> 0 1
            else if (bs1.get(c) && !bs2.get(c))
                bs2.set(c);     // 0 1 -> 1 1
        }
        for (int i = 0; i < str.length(); i++) { 
            char c = str.charAt(i);
            if (bs1.get(c) && !bs2.get(c))  // 0 1
                return i;
        }
        return -1;
    }

[NowCoder]: https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys