面试高频算法专题：继续讨论数组问题（算法村第三关黄金挑战）

数组的问题不会做，不是说明你数组没学好，而是没学好用好Hash、集合、位运算等

出现次数超过一半的数字

（剑指offer）数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如：输入如下所示的一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2；如果不存在则输出0。

排序，然后找中位数

public int moreThanHalfNum_sort(int[] array)
{
    Arrays.sort(array);
    int median = array.length / 2;

    int count = 0;  //确认中位数出现的次数
    for (int i = 0; i < array.length; i++)
    {
        if (array[i] == array[median])
        {
            count++;

            if (count > array.length / 2)
                return array[median];
        }
    }

    return 0;   //不存在超过数组长度一般的元素
}

HashMap

public int moreThanHalfNum_hash(int[] array)
{
    HashMap<Integer,Integer> ans = new HashMap<>();

    for (int i = 0; i < array.length; i++)
    {
        //key为array[i]，value为某个数的出现次数
        int newCount = ans.getOrDefault(array[i], 0) + 1;

        ans.put(array[i], newCount);

        if (ans.get(array[i]) > array.length/2)
            return array[i];
    }

    return 0;   //不存在超过数组长度一般的元素
}

只出现一次的数字

元素次数是非常重要的专题，而且各个大厂非常喜欢考察难度略大的问题。

136. 只出现一次的数字 - 力扣（LeetCode）

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

HashSet

public int singleNumber(int[] nums)
{
    HashSet<Integer> set = new HashSet<Integer>();

    for (int num : nums)
    {
        if (!set.add(num))  //若set中已存在该数字，则添加失败
            set.remove(num);    //移除重复数字，只保留出现一次的数字
    }

    //将set转换为数组，然后返回第一个元素
    return set.toArray(new Integer[set.size()])[0];
}

位运算

0与其他数字num进行异或的结果是num，两个相同的数字进行异或的结果0（即使这两个数字不相邻，也最终会被抵消——即异或运算XOR满足交换律和结合律）

按二进制位进行异或，得到最终结果

public int singleNumber_2(int[] nums)
{
    int ans = 0;
    for (int num : nums)
        ans = ans ^ num;

    return ans;
}

进阶

137. 只出现一次的数字 II - 力扣（LeetCode）

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

HashSet记录元素出现次数

public int singleNumber(int[] nums)
{
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    //记录所有元素的出现次数
    for (int num : nums)
    {
        int newCount = hashMap.getOrDefault(num,0) + 1;
        hashMap.put(num,newCount);
    }

    //寻找出现次数为1的元素
    for (int num : nums)
        if (hashMap.get(num).equals(1))
            return num;

    return 0;
}

荷兰国旗问题（颜色分类）

75. 颜色分类 - 力扣（LeetCode）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

基于冒泡排序的双指针（快慢指针）

public void sortColors(int[] nums)
{
    int slow = 0;

    //将所有的0交换到数组的最前面
    for (int fast = 0; fast < nums.length; fast++)
    {
        if(nums[fast] == 0)
        {
            int t = nums[fast];
            nums[fast] = nums[slow];
            nums[slow] = t;
            slow++;
        }
    }

    //将所有的1交换到2的前面
    for (int fast = slow; fast < nums.length; fast++)
    {
        if(nums[fast] == 1)
        {
            int t = nums[fast];
            nums[fast] = nums[slow];
            nums[slow] = t;
            slow++;
        }
    }
}

类似快速排序的三指针

自行演示这三个例子来理解代码

[0,1,1,0,0,2]
[0,1,1,0,2]
[2,0,1]

public void sortColors(int[] nums)
{
    int left = 0;
    int index = 0;
    int right = nums.length - 1;

    while (index <= right)
    {
        if (nums[index] == 0)
        {
            //将index指向的0换到左边
            swap(nums, left, index);
            //left、index同时右移一位。left、index指向不同0的情况可以被避免
            left++;
            index++;
        }
        else if(nums[index] == 2)
        {
            //将index指向的2换到右边
            swap(nums, index, right);
            //只有right左移一位，因为还无法确定换过来的是0还是1（下次循环再进行判断）
            right--;
        }
        else //nums[index] == 1时, index跳过
            index++;
    }
}

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