【D22】只出现一次的数字&移动零 （LC 136&283）

今日主题：太累了，我要划水一天。

136. 只出现一次的数字

问题描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解题思路-集合

利用HashSet中的元素不能重复的特点，

HashSet常用方法

代码实现-集合

class Solution {
    public int singleNumber(int[] nums) {
       
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            if(set.contains(num)){
                //如果元素在集合中，将它删除
                set.remove(num);
            }else{
                //如果元素不再集合中，将它添加
                set.add(num);
            }
        }

        int res = 0;
        //最后集合中剩下的元素的出现次数一定是单数
        for(Integer e : set){
            res = e;   
        }
        return res;
    }
}

解题思路-位运算

挠破头也没想出来空间复杂度为O(1)的解法，最后看了题解，发现可以通过异或运算来实现。

异或运算的三个性质

数组中的全部元素的异或运算结果即为数组中只出现一次的数字

解题思路-代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

283. 移动零

问题描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

解题思路

• 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

代码实现

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0, right = 0;
        while(right < nums.length){
            if(nums[right] != 0){
                swap(nums,left,right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int i , int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}