侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【排序, 哈希表, 数学】在长度 2N 的数组中找出重复 N 次的元素

GabrielxD
2022-05-22 / 0 评论 / 0 点赞 / 38 阅读 / 649 字 / 正在检测是否收录...

题目

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
  • numsn + 1 个 不同的 元素组成,且其中一个元素恰好重复 n

解题

方法一:排序

思路

因为在 $2n$ 个元素中有 $n+1$ 个重复元素,所以把数组排序后,$nums[n]$ 和 $nums[n - 1]$ 中必定至少有一个元素是要求的重复元素。

  • 如果排序后数组中 $nums[n]$ 与 $nums[n + 1]$ 相等,则 $nums[n]$ 必是重复的元素。
  • 如果排序后数组中 $nums[n - 1]$ 与 $nums[n - 2]$ 相等,则 $nums[n - 1]$ 必是重复的元素。

代码

class Solution {
    public int repeatedNTimes(int[] nums) {
        Arrays.sort(nums);
        int mid1 = nums[nums.length / 2 - 1], mid2 = nums[nums.length / 2];
        return mid1 == nums[nums.length / 2 - 2] ? mid1 : mid2;
    }
}

方法二:哈希表

思路

使用哈希表记录数组中元素出现的个数,如果某个元素出现超过一次,那么它就是要求的重复元素。

代码

class Solution {
    public int repeatedNTimes(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            int count = counts.getOrDefault(num, 0) + 1;
            if (count > 1) return num;
            counts.put(num, count);
        }
        return -1;
    }
}

优化

因为数据范围只有 10^4 可以使用数组代替哈希表。

class Solution {
    public int repeatedNTimes(int[] nums) {
        int[] counts = new int[10001];
        for (int num : nums) {
            if (++counts[num] > 1) return num;
        }
        return -1;
    }
}

方法三:哈希表

思路

随机取俩索引,如果这两个所以不同但指向的元素相同则该元素就是重复元素。

代码

class Solution {
    public int repeatedNTimes(int[] nums) {
        Random rand = new Random();
        while (true) {
            int idx1 = rand.nextInt(nums.length);
            int idx2 = rand.nextInt(nums.length);
            if (idx1 != idx2 && nums[idx1] == nums[idx2]) return nums[idx2]; 
        }
    }
}

方法四 数学

思路

有一半的数相等,那么排列中要么所有相同的数都不相邻,要么就必定存在相邻并相等的情形。

代码

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

评论区