第一个独特字符位置

川长思鸟来 2022-06-01 12:30 114阅读 0赞

## 题目： ##

给出一个字符串。找到字符串中第一个不重复的字符然后返回它的下标。如果不存在这样的字符，返回 -1。  
**eg：**  
给出字符串 s = “lintcode”，返回 0。  
给出字符串 s = “lovelintcode”，返回 2。

## 解： ##

## （1） ##

我的算法尝试了多次还是失败了.  
我试图用**str.indexOf（value,index）**多次迭代来完成此题目，最后发现不仅算法复杂度高，并且不能很好地实现题目的要求。如果有哪位大神看到，或者和我有同样的思路，求分享，交流。

## （2） ##

我紧接着看了网上大神的一些思路，就在这记一下：

用java写：  
**注：** **博主说**此题主要是维护一个大小为256的整型数组data.用来存储下标。（因为char范围为0~255，整型数组的默认值为0。为了和下标不冲突，我们选择将其加一进行表示。）

*  遍历整个字符串。当前的字符我们假定它为C，观察data\[C\]，（1）如果它的值为0，说明是第一次看到字符C，我们就把当前下标加一复制给data\[C\]，继续遍历；（2）如果它的值大于0，说明我们之前看到过这个字符C，所以我们需要一个常量来取代原来的下标，用于说明字符C出现过至少两次，用值-1标定，继续遍历；（3）如果它的值为-1，不用管它了，继续遍历。
 *  接下来我们迭代数组data，数组中大于0的字符都是只出现过一次的，我们只需要找出最小的那个值，然后将其减一返回即可。

public int firstUniqChar(String s) {
            if (s == null || s.length() == 0)
                return -1;
            int[] data = new int[256];
            for (int i = 0; i < s.length(); ++i) {
                char c = s.charAt(i);
                int index = i + 1;
                if (data[c] == -1)
                    continue;
                else if (data[c] == 0)
                    data[c] = index;
                else 
                    data[c] = -1;
            }
            int re = Integer.MAX_VALUE;
            for (int n : data) {
                if (n > 0)
                    re = Math.min(re, n);
            }
            return re == Integer.MAX_VALUE ? -1 : re - 1;
        }

ok，本人认为此算法很不错，简单明了，能看懂。算法复杂度n。  
感谢[原博主][Link 1]的贡献，请受小女一拜。

[Link 1]: http://ramosss.com/2017/11/12/Lintcode-646-%E7%AC%AC%E4%B8%80%E4%B8%AA%E7%8B%AC%E7%89%B9%E5%AD%97%E7%AC%A6%E4%BD%8D%E7%BD%AE/