题目一

题目描述
        给定两个排序整数数组nums1和nums2，将nums2合并为一个排序数组nums1。
        nums1和nums2中初始化的元素数量分别为m和n。
        您可以假设nums1有足够的空间(大小大于或等于m + n)来容纳nums2中的其他元素

public void merge(int[] nums1, int m, int[] nums2, int n) {
 		//合并后最后一个数的索引为m+n-1
        int i = m-1;int j = n-1;int k = m+n-1;
        while(i >= 0 && j >= 0){
        	//将两个数组中从最后一位开始比较，较大的先插入
        	//当j先等于0时，说明nums2的数字已经全部复制到nums1中，此时合并完成(说明nums1中最小的元素比nums2小)
        	//当i先等于0时，说明nums1中原来的所有数字已经复制完毕，此时进入下面的循环(说明nums1中最小的元素比nums2大)
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]; 
        }
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
    }
}

题目二 ：删除有序数组中的重复项 I

题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

 public int removeDuplicates(int[] nums) {
        int cnt = 0, n = nums.length;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) ++cnt;
            else nums[i - cnt] = nums[i];
        }
        return n - cnt;
    }

题目三：数组中数字出现的次数

题目描述：

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

题解： 分组异或思想

全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

那么这一方法如何扩展到找出两个出现一次的数字呢？

如果我们可以把所有数字分成两组，使得：

1. 两个只出现一次的数字在不同的组中；

2. 相同的数字会被分到相同的组中。

那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。

那么如何实现这样的分组呢？

算法

先对所有数字进行一次异或，得到两个出现一次的数字的异或值。

在异或结果中找到任意为 1 的位。

根据这一位对所有的数字进行分组。

在每个组内进行异或操作，得到两个数字。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int ret = 0;
        for (int n : nums) {
            ret ^= n;
        }
        int div = 1;
        while ((div & ret) == 0) {
            div <<= 1;
        }
        int a = 0, b = 0;
        for (int n : nums) {
            if ((div & n) != 0) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        return new int[]{a, b};
    }
}

复杂度分析

• 时间复杂度：O(n)，我们只需要遍历数组两次。

• 空间复杂度：O(1)，只需要常数的空间存放若干变量。

题目四：只出现一次的数字 II

题目描述：

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

解法一：

解题思路：
如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

遍历统计
此方法相对容易理解，但效率较低。

使用 与运算 ，可获取二进制数字num 的最右一位

n1​=num&i

配合 无符号右移操作 ，可获取 num 所有位的值（即 n1 ~ n_32）：

num = num >>> 1

建立一个长度为 32 的数组counts ，通过以上方法可记录所有数字的各二进制位的 1 的出现次数。

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }
}

解法二：

先对数组进行排序，依次拿相邻的两个数做异或，如果为0，说明相同，i = i+ 3，否则，该值即为要查找的那个数

    public static  int singleNumber(int[] nums) {
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++){
                if(i>=nums.length-1){
                    return nums[nums.length-1];
                }else if((nums[i] ^ nums[i+1]) == 0){
                    i+=2;
                }else{
                    return nums[i];
                }
            }
            return 0;
        }