Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

目录
  • 题目描述
  • 思路分析
  • AC 代码

题目描述

961. 在长度 2N 的数组中找出重复 N 次的元素

给你一个整数数组 nums ，该数组具有以下属性：

  • nums.length == 2 * n.
  • nums 包含 n + 1 个 不同的 元素
  • nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

提示：

2 <= n <= 5000

nums.length == 2 * n

0 <= nums[i] <= 10^4

nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

思路分析

先来复习一下2n+1：

2n+1个数字中，其中有n+1个数字是相同的，找出这个重复次数最多的数字

同归于尽法，每遍历一个元素，检查手里的元素与之是不是相同 如果相同计数+1，不相同计数-1， 如果手里没有元素，也就是当计数为0的时候，将当前的这个元素拿到手里

现在来看这个题目。2n个元素，要是按照之前那个同归于尽的做法来，最后手里不会有元素存在的，都同归于尽了 那怎么办呢？

既然没有2n+1的场景，那我们就尽量制造出这个情况

比如：[1,2,4,5,3,3,3,3]这个序列

我们就把第一个元素1为要剔除的元素 将原来的数组分成了两部分，[1,2]和 [4,5,3,3,3,3] 对后一部分的序列用同归于尽的做法，是不是就得到结果了！！

当然有人会问，1如果是结果怎么办呢，比如这个序列[1,1,1,1,2,4,5,3] 这样的情况，只需要在剔除1的时候，给1计数就行了，

最后测量1的个数是不是有n个，如果1有n个，那么结果为1，1小于n，那么结果就很明显了。

AC 代码

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int assumtp_num = A[0],assumtp_num_Count = 1;
        int temp_num,Count = 0;
        for (int i = 1; i < A.size(); ++i) {
            if(A[i]==assumtp_num)
                ++assumtp_num_Count;
            else{
                if(A[i]==temp_num)
                    ++Count;
                else{
                    if(Count==0){
                        Count = 1;
                        temp_num = A[i];
                    } else{
                        --Count;
                    }
                }
            }
        }
        //cout<<assumtp_num_Count<<endl;
        return assumtp_num_Count *2==A.size()?assumtp_num:temp_num;
    }
};

以上就是Go语言LeetCode题解961在长度2N的数组中找出重复N次元素的详细内容，更多关于Go题解长度2N数组重复元素的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go语言leetcode题解953验证外星语词典示例详解

    目录 题目描述 思路分析 AC 代码 题目描述 953. 验证外星语词典 某种外星语也使用英文小写字母,但可能顺序 order 不同.字母表的顺序(order)是一些小写字母的排列. 给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true:否则,返回 false. 示例 1: 输入:words = ["hello","leetcode"], order = "hlabcdefgi

  • 利用golang的字符串解决leetcode翻转字符串里的单词

    利用golang的字符串解决leetcode翻转字符串里的单词

    题目 给定一个字符串,逐个翻转字符串中的每个单词. 示例 1: 输入: "the sky is blue" 输出: "blue is sky the" 示例 2: 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括. 示例 3: 输入: "a good example" 输出: "exampl

  • Go/C语言LeetCode题解997找到小镇法官

    目录 题目描述 思路分析 go 代码 C语言 暴力法 题目描述 997. 找到小镇的法官 - 力扣(LeetCode) 小镇里有 n 个人,按从 1 到 n 的顺序编号.传言称,这些人中有一个暗地里是小镇法官. 如果小镇法官真的存在,那么: 小镇法官不会信任任何人. 每个人(除了小镇法官)都信任这位小镇法官. 只有一个人同时满足属性 1 和属性 2 . 给你一个数组 trust ,其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人. 如果小镇法官存在并且可

  • go语言LeetCode题解1030距离顺序排列矩阵单元格

    目录 一 描述 二 分析 三 答案 一 描述 1030. 距离顺序排列矩阵单元格 - 力扣(LeetCode) (leetcode-cn.com) 给定四个整数 row ,   cols ,  rCenter 和 cCenter .有一个 rows x cols 的矩阵,你在单元格上的坐标是 (rCenter, cCenter) . 返回矩阵中的所有单元格的坐标,并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排.你可以按 任何 满足此条件的顺序返回答案. 单元格(r1

  • go语言题解LeetCode989数组形式的整数加法

    目录 题目描述 思路分析 AC 代码 题目描述 989. 数组形式的整数加法 - 力扣(LeetCode) 整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组. 例如,对于 num = 1321 ,数组形式是 [1,3,2,1] . 给定 num ,整数的 数组形式 ,和整数 k ,返回 整数 num + k 的 数组形式 . 示例 1: 输入:num = [1,2,0,0], k = 34 输出:[1,2,3,4] 解释:1200 + 34 = 1234 示例 2: 输入:num

  • Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

    目录 题目描述 思路分析 AC 代码 题目描述 961. 在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums ,该数组具有以下属性: nums.length == 2 * n. nums 包含 n + 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素. 示例 1: 输入:nums = [1,2,3,3] 输出:3 示例 2: 输入:nums = [2,1,2,5,3,2] 输出:2 示例 3: 输入:nums = [5,1,5,

  • Go语言LeetCode题解706设计哈希映射

    目录 题目描述 思路分析 AC 代码 题目描述 706. 设计哈希映射 不使用任何内建的哈希表库设计一个哈希映射(HashMap). 实现 MyHashMap 类: MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) .如果 key 已经存在于映射中,则更新其对应的值 value . int get(int key) 返回特定的 key 所映射的 value :如果映射中不包含 key

  • go语言LeetCode题解720词典中最长的单词

    目录 一 描述 二 分析 三 答案 四 总结 一 描述 720. 词典中最长的单词 - 力扣(LeetCode) (leetcode-cn.com) 给出一个字符串数组 words 组成的一本英语词典.返回 words 中最长的一个单词,该单词是由 words 词典中其他单词逐步添加一个字母组成. 若其中有多个可行的答案,则返回答案中字典序最小的单词.若无答案,则返回空字符串. 示例 1: 输入:words = ["w","wo","wor",&

  • Go语言LeetCode题解937重新排列日志文件

    目录 一 题目描述 二 分析 三 答案 一 题目描述 937. 重新排列日志文件 - 力扣(LeetCode) (leetcode-cn.com) 给你一个日志数组 logs.每条日志都是以空格分隔的字串,其第一个字为字母与数字混合的 标识符 . 有两种不同类型的日志: 字母日志:除标识符之外,所有字均由小写字母组成 数字日志:除标识符之外,所有字均由数字组成 请按下述规则将日志重新排序: 所有 字母日志 都排在 数字日志 之前. 字母日志 在内容不同时,忽略标识符后,按内容字母顺序排序:在内容

  • 剑指offer之C语言不修改数组找出重复的数字

    1  题目 不修改数组找出重复的数字 在一个长度为N+1的数组里面的所有数字都在范围1~N范围内,所以数组至少有一个数字是重复的,请找出重复数字,但是不能修改输入的数组. 2  思路 思路1: 我们开辟一个新的数组,初始化为0,然后把原始数组每个数据的值作为下标,把新数组通过这个下标数据取出来,如果取出来是1,就说明这个下标数据重复了,如果不是,我们直接放进去,然后进行新数组值进行++操作. 思路2: 比如数据1 2 2 3 4 5 6 7, 我们先找到中间的值(1 + 7) / 2 = 4;然

  • C语言 数组中重复的数字分析及方法

    C语言 数组中重复的数字分析及方法

    C语言 数组中重复的数字解决方法: 题目:在一个长度为n的数组里的所有数字都在0-n-1的 范围内.数组中某些数字是重复的,但是不知道有几个数字重复了,也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. 解法1:对于数组进行排序,之后对于已经排序的数组进行遍历便可知道数组中重复的数字. 时间复杂度;O(nlogn); 解法2:建立一个大小为O(N)的哈希表,遍历数组中的元素并判断是否存在于哈

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • go语言题解LeetCode453最小操作次数使数组元素相等

    目录 题目描述 思路分析 AC 代码 小结 遍历数组一次 解题思路 代码 强行找规律 解题思路 代码 题目描述 原题链接 : 453. 最小操作次数使数组元素相等 - 力扣(LeetCode) (leetcode-cn.com) 给你一个长度为 n 的整数数组,每次操作将会使 n - 1 个元素增加 1 .返回让数组所有元素相等的最小操作次数. 示例 1: 输入:nums = [1,2,3] 输出:3 解释: 只需要3次操作(注意每次操作会增加两个元素的值): [1,2,3] => [2,3,3

随机推荐