LeetCode 169.多数元素(Java)

• • LeetCode 169.多数元素
  • • 1.题目描述
    • 2.示例
    • 3.我的思路分析
    • 4.插入排序题解
    • 5.希尔排序题解
    • 6.投票写法(参考大神做的)

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

我一开始想的是先开辟一个新数组，然后循环nums数组，统计各个数字出现的次数，最后循环新数组找出max元素，但是一想这样效率太慢了，而且空间复杂度太高，就没有去实现。

因为数组非空，给定的数组总是出现多数元素的，假定数组长度是奇数（已排序好），如2，1，1，2，2 。排序后的数组为 1，1，2，2，2 。数组长度/2=2，最后返回的值是 2 符合题意 。假定数组长度是偶数（已排序好），如 1，2，1，1，1，2 。排序后的数组为 1，1，1，1，2，2 。数组长度/2=3，最后返回的值是 1 符合题意，所以可以使用排序法，先排序后，最后返回nums [nums.length/2] ，即为答案。

插入排序平均时间复杂度是O(n ^2)，最好情况是O(n)，最坏情况是O(n ^2)，空间复杂度是O(1)，所以可以尝试进阶

public int majorityElement(int[] nums) {
        int insertIndex;
        int insertVal;

        int len=nums.length;
        //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < len; i++) {
            //要插入的数据
            insertVal = nums[i];

            //从已经排序的序列最右边的开始比较，找到比其小的数
            insertIndex = i;
            while (insertIndex > 0 && insertVal < nums[insertIndex - 1]) {
                nums[insertIndex] = nums[insertIndex - 1];
                insertIndex--;
            }

            //存在比其小的数，插入
            if (insertIndex != i) {
                nums[insertIndex] = insertVal;
            }
        }

        return nums[len/2];
    }

可以看到插入排序的速度太慢了！！可以尝试一下希尔排序

希尔排序排序平均时间复杂度是O(n log n)，最好情况是O(n log^2 n)，最坏情况是O(n log^2 n)，空间复杂度是O(1)，所以可以尝试进阶

public int majorityElement(int[] nums){
        int temp = 0;
        int len=nums.length;
        //增量gap，并逐渐减少增量
        for (int gap = len / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < len; i++) {
                int j = i;
                temp = nums[j];
                if (nums[j] < nums[j - gap]) {
                    while (j - gap >= 0 && temp < nums[j - gap]) {
                        //移动
                        nums[j] = nums[j - gap];
                        j -= gap;
                    }
                    //当退出while循环，就给temp找到了插入的位置
                    nums[j] = temp;
                }
            }
        }

        return nums[len/2];
    }

可以看到希尔排序速度提高了不少，但是和其他解法还是有差距

先把第一个数赋值给a，如果后面出现a，就给a投票，b++(b即为a的票数)，如果不为a，就拿走a的票数(即b–)，直到b==0后，再给a赋一个全新的值，依次下去

public int majorityElement(int[] nums){
        int a =-1;
        int b = 0;
        int len=nums.length;
        for (int i = 0; i < len; i++) {
            if(b==0){
                a=nums[i];
            }
            if (nums[i]==a){
                b++;
            }else {
                b--;
            }
        }
        return a;
    }

可以看到时间上又提高了不少

其实直接调用api里的排序算法，速度也是可观的，但是我觉得既然做算法题就尽量不用现成的api

public int majorityElement(int[] nums){
        Arrays.sort(nums);
        return nums[nums.length/2];
    }