20190811:隻出現一次的數字（四種解法）

隻出現一次的數字

• • 題目
  • 大緻思路
  • 代碼實作

題目

大緻思路

方法一：先排序，然後2個2個進行周遊，因為排序之後這個單獨的數字一定在偶數下标對應的位置，找到不相同的這兩個相鄰數字，這兩個數字中位于偶數下标的即為那個單獨的數字，如果周遊結束還沒找到，則為最後一個數字，注意周遊的時候隻周遊到長度-1處即可。

方法二：利用set集的特性，來進行實作，出現重複的就删除出set，對對碰的思想，直到周遊完，set中剩餘的那一個就是單獨的那個數字。

方法三：內插補點法，排序後，單獨的那個數字一定在偶數下标處，将所有偶數下标數字加起來減去所有奇數下标數字的和即為所求值。

方法四：異或法，該題的最佳解法：同的數字異或為0,0與任何數字異或，結果為該數字，即為那個但難度的數字

代碼實作

class Solution {
    public int singleNumber(int[] nums) {
        /*周遊法，先排序，再周遊 10ms
        Arrays.sort(nums);
        for(int i = 0;i<nums.length-1;i+=2){
            if(nums[i] != nums[i+1]){
                return nums[i];
            }
        }
        return nums[nums.length-1];
        */
        /* 方法二：利用set集的特性，來進行實作，出現重複的就删除出set，對對碰的思想，直到周遊完，set中剩餘的那一個就是           單獨的那個數字 20ms
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            if(!set.add(nums[i])){
                set.remove(nums[i]);
            }
        }
        return set.iterator().next();
        */
        /*方法三：內插補點法：排序後，單獨的那個數字一定在偶數下标處，将所有偶數下标數字加起來減去所有奇數下标數字的和，
        //即為所求的值。 10ms
        Arrays.sort(nums);
        int count = 0;
        for(int i = 0;i<nums.length;i++){
            count = i % 2 == 0 ? count+nums[i] : count-nums[i];
        }
        return count;
        */
        //*方法四：異或法，相同的數字異或為0,0與任何數字異或，結果為該數字，1ms，異或法應該為最佳解法。
        int result = 0;
        for(int i = 0;i<nums.length;i++){
            result = result ^ nums[i];
        }
        return result;
    } 
}