题目描述

找出一个在长度为N数组中重复出现的随机数字，且这个数需要在0~N的范围内，否则返回-1

算法1

暴力枚举

JAVA 代码

static class Solution {
     public int duplicateInArray(int[] nums) {
        if(nums.length==0) return -1;
        int[] equals=new int[nums.length];//存放数组中的不同数字
        int[] counts=new int[nums.length];//存放不同数字出现的次数
        int count=0;//存放不同数字的个数

        for (int i = 0; i < nums.length; i++) {
            boolean find=false;//没发现
            for (int j = 0; j < equals.length; j++) {
                if(nums[i]<0||nums[i]>nums.length) 
                    return -1;
                if(equals[j]==nums[i]) {
                    find =true;
                    counts[j]++;
                    break;
                }
            }

        if(!find) {//如果没发现，说明这个数没有出现过，就加入数组
            equals[count] =nums[i];
            counts[count]=1;
            count++;
            }
        }
        int[] c=new int[count];//存放出现多次的出现的数字的下标
        int cs=0;//记录出现多次的数的个数
        for (int i = 0; i < count; i++) {
            if(counts[i]>1) {
                c[cs]=i;
                cs++;
            }
        }
        if(cs==0) return -1;//没有一个出现多次的数，返回-1
        return equals[c[(int)Math.random()*cs]];//随机返回一个出现了多次的字符
    }
}

暴力破解

双循环

java 算法2

static class Solution {
    public int duplicateInArray(int[] nums) {
        if(nums.length==0) return -1;
        int num=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<0||nums[i]>nums.length)
                return -1;

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