排序题目:多数元素

2024-06-06 18:52
文章标签 题目 元素 排序 多数

本文主要是介绍排序题目:多数元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
      • 进阶
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法三
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:多数元素

出处:169. 多数元素

难度

2 级

题目描述

要求

给定大小为 n \texttt{n} n 的数组 nums \texttt{nums} nums,返回其中的多数元素。

多数元素是指在数组中出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{\texttt{n}}{\texttt{2}} \Big\rfloor 2n 的元素。可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例

示例 1:

输入: nums = [3,2,3] \texttt{nums = [3,2,3]} nums = [3,2,3]
输出: 3 \texttt{3} 3

示例 2:

输入: nums = [2,2,1,1,1,2,2] \texttt{nums = [2,2,1,1,1,2,2]} nums = [2,2,1,1,1,2,2]
输出: 2 \texttt{2} 2

数据范围

  • n = nums.length \texttt{n} = \texttt{nums.length} n=nums.length
  • 1 ≤ n ≤ 5 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{5} \times \texttt{10}^\texttt{4} 1n5×104
  • -10 9 ≤ nums[i] ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{nums[i]} \le \texttt{10}^\texttt{9} -109nums[i]109

进阶

你可以使用线性时间复杂度和 O(1) \texttt{O(1)} O(1) 空间复杂度解决此问题吗?

解法一

思路和算法

最直观的解法是统计数组中每个元素的出现次数,然后寻找出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 的元素。

遍历数组,使用哈希表记录每个元素的出现次数,遍历结束之后即可得到数组中每个元素的出现次数。然后遍历哈希表,对于哈希表中的每个元素得到出现次数,返回出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 的元素。

代码

class Solution {public int majorityElement(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {counts.put(num, counts.getOrDefault(num, 0) + 1);}int majority = 0;int n = nums.length;Set<Integer> set = counts.keySet();for (int num : set) {if (counts.get(num) > n / 2) {majority = num;break;}}return majority;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。遍历数组统计每个元素的出现次数需要 O ( n ) O(n) O(n) 的时间,遍历哈希表得到多数元素也需要 O ( n ) O(n) O(n) 的时间。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要创建哈希表记录每个元素的出现次数,哈希表中的元素个数不超过 n n n

解法二

思路和算法

另一个解法是将数组排序后得到多数元素。排序后的数组满足相等的元素一定出现在数组中的相邻位置,由于多数元素在数组中的出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n,因此排序后的数组中存在至少 ⌊ n 2 ⌋ + 1 \Big\lfloor \dfrac{n}{2} \Big\rfloor + 1 2n+1 个连续的元素都是多数元素,下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 的元素一定是多数元素。理由如下:

  • 如果多数元素是数组中的最小元素,则排序后的数组从下标 0 0 0 到下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 的元素都是多数元素;

  • 如果多数元素是数组中的最大元素,则排序后的数组从下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 到下标 n − 1 n - 1 n1 的元素都是多数元素;

  • 如果多数元素不是数组中的最小元素和最大元素,则排序后的数组的下标 0 0 0 和下标 n − 1 n - 1 n1 的元素都不是多数元素,多数元素的开始下标一定小于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n,结束下标一定大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n,下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 的元素一定是多数元素。

因此将数组排序之后返回下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 的元素即可。

代码

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

复杂度分析

  • 时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn),其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的时间。

  • 空间复杂度: O ( log ⁡ n ) O(\log n) O(logn),其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( log ⁡ n ) O(\log n) O(logn) 的递归调用栈空间。

解法三

思路和算法

寻找多数元素的另一种解法是摩尔投票算法,其时间复杂度是 O ( n ) O(n) O(n),空间复杂度是 O ( 1 ) O(1) O(1)

摩尔投票算法由 Robert S. Boyer 和 J Strother Moore 提出,该算法的基本思想是:在每一轮投票过程中,从数组中删除两个不同的元素,直到投票过程无法继续,此时数组为空或者数组中剩下的元素都相等。

摩尔投票算法的具体做法如下。

  1. 维护多数元素 majority \textit{majority} majority 和多数元素的出现次数 count \textit{count} count,初始时 majority \textit{majority} majority 为数组的首个元素, count = 1 \textit{count} = 1 count=1

  2. 遍历数组中除了首个元素以外的所有元素,当遍历到元素 num \textit{num} num 时,执行如下操作。

    1. 如果 count = 0 \textit{count} = 0 count=0,则将 majority \textit{majority} majority 的值更新为 num \textit{num} num,否则不更新 majority \textit{majority} majority 的值。

    2. 如果 num = majority \textit{num} = \textit{majority} num=majority,则将 count \textit{count} count 1 1 1,否则将 count \textit{count} count 1 1 1

由于这道题中多数元素总是存在,因此遍历结束之后, majority \textit{majority} majority 即为多数元素。

如果不保证多数元素一定存在,则当多数元素不存在时,遍历结束之后的 majority \textit{majority} majority 可能为数组中的任意一个元素。此时需要再次遍历数组,统计 majority \textit{majority} majority 在数组中的出现次数,当 majority \textit{majority} majority 的出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n majority \textit{majority} majority 是多数元素,当 majority \textit{majority} majority 的出现次数小于等于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor 2n 时没有多数元素。

考虑示例 1, nums = [ 3 , 2 , 3 ] \textit{nums} = [3, 2, 3] nums=[3,2,3],使用摩尔投票算法寻找多数元素的过程如下。

  1. 初始化 majority = nums [ 0 ] = 3 \textit{majority} = \textit{nums}[0] = 3 majority=nums[0]=3 count = 1 \textit{count} = 1 count=1

  2. 遍历到 nums [ 1 ] = 2 \textit{nums}[1] = 2 nums[1]=2

    1. 由于 count = 1 \textit{count} = 1 count=1,因此不更新 majority \textit{majority} majority 的值。

    2. 由于当前元素不等于 majority \textit{majority} majority,因此将 count \textit{count} count 1 1 1 count \textit{count} count 变成 0 0 0

  3. 遍历到 nums [ 2 ] = 3 \textit{nums}[2] = 3 nums[2]=3

    1. 由于 count = 0 \textit{count} = 0 count=0,因此将 majority \textit{majority} majority 的值更新为当前元素 3 3 3

    2. 由于当前元素等于 majority \textit{majority} majority,因此将 count \textit{count} count 1 1 1 count \textit{count} count 变成 1 1 1

  4. 遍历结束, majority = 3 \textit{majority} = 3 majority=3,多数元素是 3 3 3

代码

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

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 一次。

  • 空间复杂度: O ( 1 ) O(1) O(1)

这篇关于排序题目:多数元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1036946

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

遮罩,在指定元素上进行遮罩

废话不多说,直接上代码: ps:依赖 jquer.js 1.首先,定义一个 Overlay.js  代码如下: /*遮罩 Overlay js 对象*/function Overlay(options){//{targetId:'',viewHtml:'',viewWidth:'',viewHeight:''}try{this.state=false;//遮罩状态 true 激活,f

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(