AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 13. 找出数组中重复的数字--Java代码    原题链接    简单

作者: 作者的头像   木木灬 ,  2019-04-02 20:20:37 ,  阅读 1371


6



算法1

将当前位置的数值放到他的位置上去,比如{2,2,3,3,4},将nums[0]的数应该放到nums[2]上,即将该数组放到他在数组中和他角标相等的位置,每次都检查要交换的位置上的数值是否一样,如果一样,则重复,如果不一样,则交换。

时间复杂度分析:$o(n)$

JAVA 代码

    public int duplicateInArray(int[] nums) {
        int len = nums.length;
        if(nums==null||len==0)
            return -1;
        Set<Integer> set = new HashSet<>();
        for(int i =0;i<len;i++){
            if(nums[i]<0||nums[i]>len-1)
                return -1;
        }
        // Arrays.sort(nums);
        for(int i = 0;i<len;i++){
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]])
                    return nums[i];

                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }

        return -1;
    }

算法2

将数组进行排序,将当前位置和下一位置的数字进行对比,如果一样,则方法结束并返回

JAVA 代码

    public int duplicateInArray(int[] nums) {
        int len = nums.length;
        if(nums==null||len==0)
            return -1;
        Set<Integer> set = new HashSet<>();
        for(int i =0;i<len;i++){
            if(nums[i]<0||nums[i]>len-1)
                return -1;
        }
        Arrays.sort(nums);
        for(int i = 0;i<len-1;i++){
            if(nums[i]==nums[i+1])
                return nums[i];
        }

        return -1;
    }

算法3

用hashset的add方法,如果哈希表中没有这个数据,则返回true并加入,如果有,则返回false

JAVA 代码

    public int duplicateInArray(int[] nums) {
        int len = nums.length;
        if(nums==null||len==0)
            return -1;
        Set<Integer> set = new HashSet<>();
        for(int i =0;i<len;i++){
            if(nums[i]<0||nums[i]>len-1)
                return -1;
        }
        Arrays.sort(nums);
        for(int i = 0;i<len;i++){
            if(!set.add(nums[i]))
                return nums[i];
        }

        return -1;
    }

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息