宫水三叶的刷题日记

V1

2022/06/20阅读:11主题:前端之巅同款

【宫水三叶的刷题日记】961. 在长度 2N 的数组中找出重复 N 次的元素

题目描述

这是 LeetCode 上的 961. 在长度 2N 的数组中找出重复 N 次的元素 ,难度为 简单

Tag : 「模拟」、「计数」、「构造」、「哈希表」

给你一个整数数组 nums ,该数组具有以下属性:

  • nums 包含 个 不同的 元素
  • nums 中恰有一个元素重复

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

示例 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 <= 50004
  • nums 个 不同的 元素组成,且其中一个元素恰好重复

计数模拟

根据题目给定的三个条件可推断出:数组中仅有一个元素出现多次,其余元素均出现一次。

又利用数据范围为 ,我们可以使用数组充当哈希表进行计数,当出现一个 重复出现即是答案。

代码:

class Solution {
    int[] cnts = new int[10010];
    public int repeatedNTimes(int[] nums) {
        for (int x : nums) {
            if (++cnts[x] > 1return x;
        }
        return -1;
    }
}
  • 时间复杂度:
  • 空间复杂度:

构造共性

假设重复出现的数字是 ,数字 重复了 次,要将这 个相同的 间隔开,需要 个额外数字,而实际上我们除 以外还有 个额外数字(数字总数为 个),因此在我们所能构造出的所有排列方式中,最多 使相邻 之间间隔了 个额外数字。

对于每个 而言,我们检查往前的三个位置(若有),如果有重复相等情况,说明当前的 即是答案。

代码:

class Solution {
    public int repeatedNTimes(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (i - 1 >= 0 && nums[i - 1] == t) return t;
            if (i - 2 >= 0 && nums[i - 2] == t) return t;
            if (i - 3 >= 0 && nums[i - 3] == t) return t;
        }
        return -1;
    }
}
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.961 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关的资料可访问排版精明的 合集新基地 🎉🎉

分类:

后端

标签:

数据结构与算法

作者介绍

宫水三叶的刷题日记
V1