Leetcode 字符串中的第一个唯一字符

一颗蔬菜 2019-09-06 PM 34℃ 0条

原题链接

第一感觉就是非要用Map来解决,因为涉及到重复元素,而且还需要取索引。我的解决办法朴实无华:

1.将字符串转化为字符数组

2.将字符数组的字符作为Key,索引作为key插入到Map中。

3.将插入失败的key-value的key值存入Set中,插入失败的即重复的。

4.遍历Set,将Map中这些有过重复key的元素全部删掉。

5.删掉重复元素后,剩下的都是唯一字符的key-value

6.将Map中value存入Collection中,然后排序一下

7.排序后的第一个元素就是我们想要的结果

第一遍提交时我犯了一个错误,就是只要检测到重复就当场把它从Map中删除,这么做就忽略了一种情况:假如一个字符出现奇数次,当场删除是没有用的,因为下次出现就检测不到它是重复的了。因此,我决定把所有重复的存入到Set中,所有key-value插入完成后,一次性删除这些重复字符的key-value,这样剩下的就都是唯一字符了。

/*
执行用时 :103 ms, 在所有 Java 提交中击败了32.29%的用户
内存消耗 :48.9 MB, 在所有 Java 提交中击败了33.32%的用户
*/
import java.util.*;
class Solution {
    public int firstUniqChar(String s) {
        char[] str = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < str.length; i++ ) {
            if(map.put(str[i], i) != null) {
               // 将重复的元素写入到Set中
               set.add(str[i]);
            }
        }
       Iterator<Character> iterator = set.iterator(); // 删除重复元素
       while(iterator.hasNext()) {
           map.remove(iterator.next());
       }
       if (!map.isEmpty()){
            Collection<Integer> c = map.values();
            Object[] obj = c.toArray();
            Arrays.sort(obj);
            System.out.println(obj[0]);
            return (Integer)obj[0]; 
        }
        return -1;
    }
}

接着我们来看一下大佬是怎么解决这个问题吧

/*
执行用时 :2 ms, 在所有 Java 提交中击败了99.58%的用户
内存消耗 :48.9 MB, 在所有 Java 提交中击败了33.54%的用户
*/
class Solution {
     public int firstUniqChar(String s) {
        int index = -1;
        //反过来,只有26个字符
        for (char ch = 'a'; ch <= 'z'; ch++) {
            int beginIndex = s.indexOf(ch);
            // 从头开始的位置是否等于结束位置,相等说明只有一个,
            if (beginIndex != -1 && beginIndex == s.lastIndexOf(ch)) {
                //取小的,越小代表越前。
                index = (index == -1 || index > beginIndex) ? beginIndex : index;
            }
        }
        return index;
    }
}

看了5分钟查看明白index = (index == -1 || index > beginIndex) ? beginIndex : index; 中的index == 1是怎么回事,这个条件是服务于第一个唯一元素第一次出现的位置的,因为此时index一定是小于beginIndex

标签: 算法

非特殊说明,本博所有文章均为博主原创。