LeetCode 腾讯精选50题--求众数

ゝ一纸荒年。 2023-06-05 05:53 3阅读 0赞

由于众数是指数组中相同元素的个数超过数组长度的一半，所以有两种思路，一. 先排序，后取排序后的数组的中间位置的值；二. 统计，设定一个变量统计相同元素出现的次数，遍历数组，若与选定的元素相同，统计变量加一，否则减一，如果统计变量减为0，则换下一个元素作为对比元素，这么做可行的原因是众数的数量超过数组一半的前提下，统计变量的累加次数是会大于减少次数的，这也就可以保证遍历完数组后统计变量值大于0对应的元素是所要找的众数。

时间复杂度对比：

排序，这里采用快排，时间复杂度为O(NlogN)

统计，时间复杂度为O(N)

排序的代码实现：

1 class Solution {
     2    public int majorityElement(int[] nums) {
     3 
     4         if(nums.length <= 2){
     5             return nums[0];
     6         }
     7         int boundary = nums.length/2;
     8         quickSort(nums,0,nums.length-1,boundary);
     9 
    10         return nums[boundary];
    11     }
    12 
    13     private void quickSort(int[] nums,int left,int right,int boundary){
    14         if(left >= right){
    15             return;
    16         }
    17         int pivot = median(nums,left,right);
    18         int center = (left+right)/2;
    19         int i = left,j=right-1;
    20         if(i < j){
    21             while (true){
    22                 while (nums[++i] < pivot ){
    23                 }
    24 
    25                 while (nums[--j] > pivot){
    26 
    27                 }
    28                 if(i >= j){
    29                     break;
    30                 }else {
    31                     swap(nums,i,j);
    32                 }
    33             }
    34         }
    35         swap(nums,i,right-1);
    36         quickSort(nums,left,i-1,boundary);
    37         quickSort(nums,i+1,right,boundary);
    38     }
    39 
    40     private int median(int[] nums,int left,int right){
    41         int center = (left+right)/2;
    42         if(nums[left] > nums[center]){
    43             swap(nums,left,center);
    44         }
    45         if(nums[left] > nums[right]){
    46             swap(nums,left,right);
    47         }
    48         if(nums[center] > nums[right]){
    49             swap(nums,center,right);
    50         }
    51         swap(nums,center,right-1);
    52         return nums[right-1];
    53     }
    54 
    55     private void swap(int[] nums,int left,int right){
    56         int temp = nums[left];
    57         nums[left] = nums[right];
    58         nums[right] = temp;
    59     }
    60 }

统计的代码：

class Solution {
        public int majorityElement(int[] nums) {
            int count=1;
            int index = nums[0];
            for(int i=1; i<nums.length; i++){
                if(nums[i] == index){
                    count++;
                }else{
                    count--;
                    if(count==0){
                        index = nums[i+1];
                    }
                }
            }
            return index;
        }
    }

转载于:https://www.cnblogs.com/Kaithy-Rookie/p/11338949.html