[LeetCode] 列表找唯一(元素或者序号)

￡神魔★判官ぃ 2022-05-18 06:41 117阅读 0赞

# 出处 #

> [只出现一次的数字][Link 1]  
> [字符串中的第一个唯一字符][Link 2]

# 分析 #

关于找唯一，简单使用二重循环会出现超时问题，只能使用别的方式。

*  简单版  
    建立一个相同长度的数组，标记每个元素是否曾经出现过，如果是标记为true，否则为false。之后遍历这个数组，如果出现false，返回即可。

class Solution {
        public int firstUniqChar(String s) {
            if(s == null || "".equals(s)) {
                return -1;
            } else {
                char[] chars = s.toCharArray();
                int[] nums = new int[chars.length];
                for(int i=0;i<chars.length;i++) {
                    nums[i] = (int) chars[i];
                }
                boolean[] mirror = new boolean[nums.length];
                for(int i=0;i<nums.length;i++) {
                    boolean match = false;
                    for(int j=0;j<nums.length;j++) {
                        if(i != j && nums[i] == nums[j]) {
                            match = true;
                            break;
                        }
                    }
                    mirror[i] = match;          
                }
                for(int i=0;i<nums.length;i++) {
                    if(!mirror[i]) {
                        return i;
                    }
                }
                return -1;
            }
        }
    }

*  进阶版  
    通过位异或方式计算，初始状态给0，`a^a=0，a^0=a` 因此最后留下的肯定是唯一的数字～

class Solution {
        public int singleNumber(int[] A) {
            if (A == null || A.length == 0) {
                return -1;
            }
            int rst = 0;
            for (int aA : A) {
                rst ^= aA;
            }
            return rst;
        }
    }

# 其它 #

另一个题 [字符串中的第一个唯一字符][Link 2]  
将String变为char\[\]，然后变成int\[\] 就可以按照上边的方法解决了。

[Link 1]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
[Link 2]: https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/34/