Leetcode 961. N-Repeated Element in Size 2N Array

小咪咪 2021-12-21 02:11 55阅读 0赞

**Problem:**

In a array `A` of size `2N`, there are `N+1` unique elements, and exactly one of these elements is repeated N times.

Return the element repeated `N` times.

**Example 1:**

Input: [1,2,3,3]
    Output: 3

**Example 2:**

Input: [2,1,2,5,3,2]
    Output: 2

**Example 3:**

Input: [5,1,5,2,5,3,5,4]
    Output: 5

**Note:**

1.  `4 <= A.length <= 10000`
2.  `0 <= A[i] < 10000`
3.  `A.length` is even

**Solution**:

这道题是首个我写入博客的easy题，因为这道题的解法思路太巧妙了，计数的做法就不说了，主要来讲线性时间复杂度和常量空间复杂度的解法。这道题和摩尔筛选法不同，摩尔筛选法适用于重复数字大于数组长度一半的情况，这里是等于。这道题有一个隐藏规律，我们只要**找出一对重复的数字就行了，并且至少存在一个长度为4的子数组里存在一对重复的数字**。如果说数组长度非常长，那么最大的相同数字间的最小间隔为2，比如\{0,1,0,2,0,3,0,4...\}，之所以为3（即长度为4的子数组存在重复数字）是因为要考虑特殊情况如\{0,1,2,0\}。

**Code:**

1 class Solution {
     2 public:
     3     int repeatedNTimes(vector<int>& A) {
     4         for (int k = 1; k <= 3; ++k)
     5             for (int i = 0; i < A.size() - k; ++i)
     6                 if (A[i] == A[i+k])
     7                     return A[i];
     8         return -1;
     9     }
    10 };

转载于:https://www.cnblogs.com/haoweizh/p/10412205.html

发表评论取消回复

表情：

评论列表（有 0 条评论，55人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 540. Single Element in a Sorted Array

文章作者：Tyan 博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1] 1. Description ![Single E

蔚落/ 2022年09月09日 00:13/ 0 赞/ 46 阅读

相关 Facebook面试题 Find first k common elements in n sorted arrays

> Given n sorted arrays, find first k common elements in them. > E.g. the common eleme

淩亂°似流年/ 2022年07月13日 07:11/ 0 赞/ 100 阅读

相关【leetcode】215. Kth Largest Element in an Array

【leetcode】215. Kth Largest Element in an Array Find the kth largest element in an uns

叁歲伎倆/ 2022年07月08日 19:26/ 0 赞/ 154 阅读

相关 leetcode 540. Single Element in a Sorted Array

1.题目 Given a sorted array consisting of only integers where every element appears twi

末蓝、/ 2022年06月08日 02:51/ 0 赞/ 108 阅读

相关 LeetCode 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest eleme

怼烎@/ 2022年06月02日 11:52/ 0 赞/ 105 阅读

相关 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest e

落日映苍穹つ/ 2022年04月25日 03:16/ 0 赞/ 110 阅读

相关 Leetcode 961. N-Repeated Element in Size 2N Array

Problem: In a array `A` of size `2N`, there are `N+1` unique elements, and exactly o

小咪咪/ 2021年12月21日 02:11/ 0 赞/ 56 阅读

相关 Find First and Last Position of Element in Sorted Array - LeetCode

目录题目链接注意点解法小结题目链接 [Find First and Last Position of Element in Sort

我会带着你远行/ 2021年09月30日 15:06/ 0 赞/ 158 阅读

相关 [matrix/leetcode](sort)Kth Largest Element in an Array-快速排序

Kth Largest Element in an Array-快速排序前言题干代码前言这道题当作是快速排序的一

迈不过友情╰/ 2021年09月28日 07:46/ 0 赞/ 187 阅读

相关 LeetCode 961. N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elem...

灰太狼/ 2021年03月28日 12:39/ 0 赞/ 383 阅读