每日一题-10th

⭐每日一题⭐专栏

written by SJTU-XHW

本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！

Leetcode 442. 数组中重复的数据

题干

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现一次或两次。请你找出所有出现两次的整数，并以数组形式返回。你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例

示例 1：

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

示例 2：

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

示例 3：

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

思路

输入输出不算额外空间 [😂]，所以哈希一下，不用哈希表类

实现

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int len = nums.size();
        vector<int> ans; ans.resize(len, 0);
        for (int x : nums) ++ans[x - 1];
        int oneN = 0;
        for (int i = 0; i < len; ++i) {
            if (ans[i] == 2) ans[i - oneN] = i + 1;
            else ++oneN;
        }
        ans.resize(len - oneN);
        return ans;
    }
};