写点什么

【LeetCode】在长度 2N 的数组中找出重复 N 次的元素 Java 题解

作者:HQ数字卡
  • 2022 年 5 月 21 日
  • 本文字数:628 字

    阅读完需:约 2 分钟

题目描述

给你一个整数数组 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 <= 5000nums.length == 2 * n0 <= nums[i] <= 10000nums 由 n + 1 个 不同的 元素组成,且其中一个元素恰好重复 n 次
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/n-repeated-element-in-size-2n-array著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法题目是数组处理题目,需要找到数组中重复出现的元素个数。我们首先可以使用 hashmap 遍历整个数组,记录每一个元素出现的个数,找到出现个数大于 1 的个数,即位答案。

  • 由于是数组题目,我们可以参考数值的取数范围 0 <= nums[i] <= 10000,定义一个 cnt 数组,记录元素出现的个数。具体实现代码如下:

通过代码

class Solution {    public int repeatedNTimes(int[] nums) {        int ans = 0;        int[] cnt = new int[10001];         for (int num : nums) {            cnt[num]++;            if (cnt[num] > 1) {                ans = num;            }        }        return ans;    }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n), 空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】在长度 2N 的数组中找出重复 N 次的元素Java题解_LeetCode_HQ数字卡_InfoQ写作社区