leetcode 442. 数组中重复的数据(java)

这篇具有很好参考价值的文章主要介绍了leetcode 442. 数组中重复的数据(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode 442. 数组中重复的数据

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-all-duplicates-in-an-array

题目描述

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

示例 1:
输入:nums = [4,3,2,7,8,2,3,1]
输出:[2,3]

示例 2:
输入:nums = [1,1,2]
输出:[1]

示例 3:
输入:nums = [1]
输出:[]

提示:
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
nums 中的每个元素出现 一次 或 两次

原地哈希

由于给定的 n 个数都在 [1,n] 的范围内,如果有数字出现了两次,就意味着 [1,n] 中有数字没有出现过。

因此,我们可以尝试将每一个数放在对应的位置。由于数组的下标范围是 [0,n−1],我们需要将数 i 放在数组中下标为 i−1 的位置:

如果 i 恰好出现了一次,那么将 i 放在数组中下标为 i−1 的位置即可;
如果 ii 出现了两次,那么我们希望其中的一个 i 放在数组下标中为 i−1 的位置,另一个 i 放置在任意「不冲突」的位置 jj。也就是说,数 j+1 没有在数组中出现过。

这样一来,如果我们按照上述的规则放置每一个数,那么我们只需要对数组进行一次遍历。当遍历到位置 ii 时,如果nums[i]−1 != i ,说明 nums[i] 出现了两次(另一次出现在位置 num[i]−1),我们就可以将 num[i] 放入答案。

放置的方法也很直观:我们对数组进行一次遍历。当遍历到位置 i 时,我们知道 nums[i] 应该被放在位置 nums[i]−1。因此我们交换 num[i]和 nums[nums[i]−1] 即可,直到待交换的两个元素相等为止。

代码演示

   /**
     * 数组中重复的数据
     * @param nums
     * @return
     */
    public List<Integer> findDuplicates(int[] nums) {
        for (int i = 0; i < nums.length;i++){
            while (nums[i] != nums[nums[i] - 1] ){
                swap(nums,i,nums[i] - 1);
            }
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length;i++){
            if (nums[i] - 1 != i){
                ans.add(nums[i]);
            }
        }
        return ans;
    }

    /**
     * 交换
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[]nums,int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

原地哈希算法

leetcode 287. 寻找重复数文章来源地址https://www.toymoban.com/news/detail-555931.html

到了这里,关于leetcode 442. 数组中重复的数据(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之数组: Leetcode 914. 卡牌分组 (Typescript版)

    卡牌分组 https://leetcode.cn/problems/x-of-a-kind-in-a-deck-of-cards/ 描述 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X = 2 时返回 true。

    2024年02月02日
    浏览(41)
  • 数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

    数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此

    2024年02月07日
    浏览(48)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(75)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(47)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(43)
  • 【数据结构OJ题】删除有序数组中的重复项

    原题链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 用 双指针算法, 定义两个变量src和dst,一开始让src和dst指向num[ ]数组的第一个元素,再使用if语句判断。 如果nums[src]==nums[dst],就让src指向下一位,即src++。如果nums[src]!=

    2024年02月14日
    浏览(39)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode667. 优美的排列 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 题目要求我们返回一个数组长度为n的数组,必须含有1~n的所有数,并且从左到右,相邻的元素依次相减,它们的差,必

    2024年01月25日
    浏览(48)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(56)
  • java数据结构与算法刷题-----LeetCode96. 不同的二叉搜索树

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只

    2024年01月21日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包