169.多数元素

1.利用中位数性质

2.哈希表

3.摩尔投票法   与本数相同记为1 不同记为-1

class Solution { public:     int majorityElement(vector<int>& nums) {         int x = 0, votes = 0;         for(int num : nums){             if(votes == 0) x = num;             votes += (num == x ? 1 : -1);         }         return x;     } }; 

func majorityElement(nums []int) int {     flag,ans,tmp:=0,0,0     for i:=0;i<len(nums);i++{         if flag==0{             ans=nums[i]         }         if ans==nums[i]{             tmp=1         }else{             tmp=-1         }         flag+=tmp     }     return ans } 

  

  

推荐这些文章:

算法 原地删除指定元素 不能创建新的数组空间

int removeElement(vector<int>& nums, int val) {
int k=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]!=val)
{
nums[k++]=nums[i];
}
}
return k;

 

...

数组元素查找

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
遍历法:

class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] >= target) {
retur...

s1.5 力扣之存在重复元素

我们可以先对数组进行排序,然后再比较。因为排序之后如果有相同的,那么相同的值肯定是挨着的,我们只需要在排序之后两两比较即可

static void Main(string[] args)
{
int[] nums = { 1, 1, 2,6,5,2,1 };
var flag = containsDuplicate(nums);
}

static bool containsDuplicate(int[] nums)
{
Array.Sort(nums);
...

leetcode-2016. 增量元素之间的最大差值

题目

示例

我的解答
class Solution:
def maximumDifference(self, nums: List[int]) -> int:
max = -1
n =len(nums)

for i in range(0,n)://range的取值是左闭右开
for j in range(i+1,n):
res = nums[j]-nums[i];
if res>max:
...

LeetCode数据结构入门——217存在重复的元素

题目意思很清楚,判断数组中是否有重复值,但是快一年过去了,算法思路几乎为0
做法一:排序后判断前后是否一致,代码如下:
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
flag = False
for i in range(len(nums)):
if i+1<len(nums) and nums[i] == nums[i+1]:
flag = True
...

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组

var threeSum = function(nums) {let ans = [];const len = nums.length;if(nums == null || len < 3) return ans;nums.sort((a, b) => a - b); // 排序for (let i = 0; i < len ; i++) {if(nums[i] > 0) break; // 如果当前数字大于0,则三数之和一定大于0,所以结束循环if(i > 0 && nums[i] == nums[i-1]) continue; // 去重le...

剑指 Offer 03. 数组中重复的数字

class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);

for(int i=0;i<nums.length-1;i++){
if(nums[i]==nums[i+1]){
return nums[i];
}
}

return 0;

}
}

 

...

Leetcode 169. 多数元素 简单

169. 多数元素
题目:
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3]
输出:3
思路:
使用计数器统计相同元素出现的个数,如果--count<0,替换记录的元素
因为出现次数大于n/2,因此最后的记录元素就是结果

class Solution {
public:
int majorityElement(vector<int>& nums) {
...

C

#include<bits/stdc++.h>
using namespace std;
int a[10];
int x,y,z;
int main()
{
int n;
for (int i = 1;i <= n;i ++) cin >> a[i];
int max = 0;
for (int i = 1;i <= n-2;i ++)
{
bool flag = false;
x = 0;
for (int j = 1;j <= i;j ++) x += a...

腾讯五十题 No.44 除自身以外数组的乘积

题目链接

class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
int left = 1;
//让每个数等于自己左边所有数的乘积
for(int i = 0;i<n;i++){
ans[i] = left;
left *= nums[i];
}
int righ...

文章标题:169.多数元素
文章链接:https://www.dianjilingqu.com/3753.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>