专栏首页后端CoderLeetCode45|数组中重复的数据

LeetCode45|数组中重复的数据

1,问题简述

给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

2,示例

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

3,题解思路

数组的使用

4,题解程序

 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindDuplicatesTest {
    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
        List<Integer> integerList = findDuplicates(nums);
        System.out.println("integerList = " + integerList);
    }

    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;

        }
        int maxValue = Arrays.stream(nums).max().getAsInt();
        int[] array = new int[maxValue + 1];
        for (int num : nums) {
            array[num]++;
        }
        for (int i = 0, length = array.length; i < length; i++) {
            if (array[i] == 2) {
                list.add(i);
            }
        }

        return list;
    }
}

5,题解程序图片版

6,总结

数组的特点就是访问快,数组空间不可动态扩容,访问快在于根据数组下标进行确定元素的位置,相比较于链表获取数组元素的时间复杂度在O(1),链表由于节点的关系,查找某个元素的时间复杂度为O(n)

本文分享自微信公众号 - WwpwW(gh_245290c1861a),作者:后端Coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode72|前K个高频元素

    hashMap键值对集合加上堆排序的使用,也算是堆,即优先级队列的使用吧,一般自己的写法都是很常规的写法,所以看懂java语法就知道怎么个意思了。

    后端Coder
  • LeetCode34|数组中的第k个最大元素

    请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    后端Coder
  • LeetCode41|数组中数组出现的次数

    请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    后端Coder
  • 【LeetCode之C#解法】 移动零、爬楼梯

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    李明成
  • LeetCode72|前K个高频元素

    hashMap键值对集合加上堆排序的使用,也算是堆,即优先级队列的使用吧,一般自己的写法都是很常规的写法,所以看懂java语法就知道怎么个意思了。

    后端Coder
  • Android技能树 — 排序算法基础小结

    现在安卓面试,对于算法的问题也越来越多了,要求也越来越多,特别是排序,基本必考题,而且还动不动就要手写,所以陆续要写算法的文章,也正好当自己学习。o(╥﹏╥)o

    青蛙要fly
  • LeetCode第七天

    ==数组 Medium== 40.(162)Find Peak Element ? JAVA //斜率思想,二分法 class Solution { p...

    郭耀华
  • No.015 3Sum

    15. 3Sum Total Accepted: 131800 Total Submissions: 675028 Difficulty: Medium   G...

    mukekeheart
  • LeetCode 189. 旋转数组(环形替换)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rotate-array 著作权归领扣网络所有。商业...

    Michael阿明
  • Leetcode 674. Longest Continuous Increasing Subsequence

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan

扫码关注云+社区

领取腾讯云代金券