专栏首页用户4352451的专栏【LeetCode】找出数组中重复的数字day01

【LeetCode】找出数组中重复的数字day01

题目

  • 找出数组中重复的数字。
  • 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,
  • 但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
  • 示例 1:
  • 输入:
  • [2, 3, 1, 0, 2, 5, 3]
  • 输出:2 或 3

  • 限制:
  • 2 <= n <= 100000

解题思路

  1. 暴力搞,双层for循环,第一层的第一个元素和全数组比较。遇到就return
  2. 空间换时间,那就是利用set的属性不可以进行重复add元素。则会fasle,那就将这个重复元素return
  • 这里需要注意的是set在进行add得时候其中检查元素重复的复杂度是多少呢?
  • 其中hashSet的add是通过HashMap的key来实现的那么我们了解一下hashMap的putVal()的源码
  • 在put的时候我们会进行插入这个最坏复杂度也在O(n)所以也就是O(n)
  1. 将数组进行排序,然后前后比较,其中java中Arrays.sort使用了两种排序方法,快速排序和优化的合并排序。那就是sort的时间复杂度为O(NlogN) for循环比较是O(n) 算下来也是O(NlogN
  2. 上面的计算复杂度的思路不准确,仅供参考
package linkedandlist;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @authoryuanxindong
 * @date: 2020/6/14 8:40 下午
 *
 */

public class FinadListRePeatNum {
    public static void main(String[] args) {
        int[] nums = new int[]{
                2, 3, 1, 0, 2, 53
        };
        int repeatNumberV1 = findRepeatNumberV1(nums);
        System.out.println("重复数字1:" + repeatNumberV1);
        int repeatNumberV2 = findRepeatNumberV2(nums);
        System.out.println("重复数字2:" + repeatNumberV2);
        int repeatNumberV3 = findRepeatNumberV3(nums);
        System.out.println("重复数字3:" + repeatNumberV3);

    }


    /**
     * 暴力遍历对比
     * 时间复杂度为 O(n^2)
     */
    private static int findRepeatNumberV1(int[] nums) {
        if (nums == null) {
            return -1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return -1;
    }

    /**
     * 空间换时间使用set的特性来判断是否有重复
     *
     * @param nums
     * @return 时间复杂度为O(n)
     */
    private static int findRepeatNumberV2(int[] nums) {
        if (nums == null) {
            return -1;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }
    /**
     * 先通过将数组排序,再进行便利比较前后元素。等于就说明重复
     * 排一次顺序是logn,for循环便利一次是N
     * 时间复杂度:O(NlogN)
     */
    private static int findRepeatNumberV3(int[] nums) {
        if (nums == null) {
            return -1;
        }

        Arrays.sort(nums);
        for (int i = 0 ; i< nums.length; i++) {
            if (nums[i] == nums[i + 1]) {
                return nums[i];
            }
        }
        return -1;
    }

    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】两数之和day09

    居士
  • SpringBoot的事务传播机制

    @Transactional(propagation = Propagation.REQUIRED)

    居士
  • 【leetCode】斐波那契数列day06

    https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

    居士
  • 查找数组中两数之和等于指定的数

    题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Melody132
  • 剑指Offer题解

    在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字,但不能修改输入的数组。 例如输...

    星如月勿忘初心
  • 【LeetCode】136. Single Number

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】两数之和

    Jacob丶
  • 哈希表-LeetCode 217、219、220、232(hashset、hashmap)

    给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    算法工程师之路
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • Largest Number Greater Than Twice of Others

    思路1: 非排序,如果存在一个数,比其他任何数的两倍还大必然是最大数。时间复杂度为O(n2)O(n^2)

    用户1147447

扫码关注云+社区

领取腾讯云代金券