面试经典算法系列之数组/字符串2 -- 多数元素

2024-04-24 08:52

本文主要是介绍面试经典算法系列之数组/字符串2 -- 多数元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

面试经典算法题34-多数元素

LeetCode.169
阿Q技术站

问题描述

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

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

示例 2:

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

思路

  1. 初始化候选多数元素 candidate 和其出现次数 count
  2. 遍历数组,对于每个元素:
    • 如果 count 为0,则将当前元素设为候选多数元素,并将 count 设为1。
    • 否则,如果当前元素等于候选多数元素,则将 count 加1,否则将 count 减1。
  3. 返回候选多数元素 candidate

图解

阿Q作

参考代码

C++
#include <iostream>
#include <vector>using namespace std;class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = nums[0]; // 初始化候选多数元素为数组第一个元素int count = 1; // 初始化候选多数元素的出现次数为1// 遍历数组for (int i = 1; i < nums.size(); ++i) {if (count == 0) {candidate = nums[i]; // 更新候选多数元素count = 1; // 重置出现次数为1} else if (nums[i] == candidate) {count++; // 候选多数元素出现,增加出现次数} else {count--; // 候选多数元素未出现,减少出现次数}}return candidate; // 返回候选多数元素}
};int main() {vector<int> nums = {3, 2, 3}; // 输入数组Solution solution;int result = solution.majorityElement(nums); // 查找多数元素cout << "多数元素:" << result << endl; // 输出结果return 0;
}
Java
import java.util.*;class Solution {public int majorityElement(int[] nums) {int candidate = nums[0]; // 初始化候选多数元素为数组第一个元素int count = 1; // 初始化候选多数元素的出现次数为1// 遍历数组for (int i = 1; i < nums.length; ++i) {if (count == 0) {candidate = nums[i]; // 更新候选多数元素count = 1; // 重置出现次数为1} else if (nums[i] == candidate) {count++; // 候选多数元素出现,增加出现次数} else {count--; // 候选多数元素未出现,减少出现次数}}return candidate; // 返回候选多数元素}public static void main(String[] args) {int[] nums = {3, 2, 3}; // 输入数组Solution solution = new Solution();int result = solution.majorityElement(nums); // 查找多数元素System.out.println("多数元素:" + result); // 输出结果}
}
Python
from typing import Listclass Solution:def majorityElement(self, nums: List[int]) -> int:candidate = nums[0] # 初始化候选多数元素为数组第一个元素count = 1 # 初始化候选多数元素的出现次数为1# 遍历数组for i in range(1, len(nums)):if count == 0:candidate = nums[i] # 更新候选多数元素count = 1 # 重置出现次数为1elif nums[i] == candidate:count += 1 # 候选多数元素出现,增加出现次数else:count -= 1 # 候选多数元素未出现,减少出现次数return candidate # 返回候选多数元素# 测试
nums = [3, 2, 3] # 输入数组
solution = Solution()
result = solution.majorityElement(nums) # 查找多数元素
print("多数元素:", result) # 输出结果

这篇关于面试经典算法系列之数组/字符串2 -- 多数元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自