技巧栏练习题

136. 只出现一次的数字

题干中要求做到线性时间复杂度和常数空间复杂度。

考虑使用位运算。使用异或运算有以下三个性质：

任何数和0 做异或运算，结果仍然是原来的数。

任何数和其自身做异或运算，结果是 0。

异或运算满足交换律和结合律。

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

169. 多数元素

可以使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

class Solution {
    public int majorityElement(int[] nums) {
        // Arrays.sort(nums);
        // return nums[nums.length/2];
        // int votes =0;
        // int candidate=0;
        // for(int num :nums){
        //     if(votes == 0){
        //         candidate = num;
        //     }
        //     votes += (num == candidate) ? 1 : -1;
        // }
        // return candidate;
        int win=nums[0];
        int count=1;
        for(int i=1;i=nums[i+1]){
            i--;
        }
        // 2.找到较大的数
        if(i>=0){
            int j=nums.length-1;
            while(j>=0 && nums[i]>=nums[j]){
                j--;
            }
            // 3.交换
            swap(nums,i,j);
        }
        // 4.翻转
        reverse(nums,i+1);
    }
    public void swap(int[] nums, int i, int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    public void reverse(int[] nums, int start){
        int left = start, right = nums.length-1;
        while(leftf(n)。从下标为 0 出发，就可以产生一个类似链表一样的序列。 
1.数组中有一个重复的整数  链表中存在环
2.找到数组中的重复整数  找到链表的环入口
 
class Solution {
    public int findDuplicate(int[] nums) {
        // 这里已经从起点0跳过一步了
        int slow=nums[0];
        int fast=nums[nums[0]];
        // 1.找到快慢指针相遇点
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        // 2.找到入环口
        // 将快指针移回起点0，与慢指针同步移动
        fast=0;
        while(fast!=slow){
            fast=nums[fast];
            slow=nums[slow];
        }
        // 返回指针位置
        return fast;
    }
}
 
3.原地哈希（如：41. 缺失的第一个证书-）
 
class Solution {
    public int findDuplicate(int[] nums) {
        for(int i=0; i