数组找出重复的数字,Java代码实现和思路分享

KLQ 2020-04-15 09:52:47 java常见问答 7217

下面要给大家分享的是在数组中找出任意一个重复数字的Java代码实现和思路,具体例举了4种代码实现和思路,可以供给大家参考哦。

题目:

在一个长度是n的数组当中,所有的数字都在0到n-1的范围之内。

数组当中,有一些数字是重复的,但是,不知道具体有几个数字重复,也不知道,每一个数字重复了多少次。

请找出数组当中的任意一个重复的数字。

例:

假如,输入的长度是7的数组{2,3,1,0,2,5,3},则,对应的输出是第一个重复的数字2。

思路1

代码实现:

//boolean只占一位,所以还是比较省的
public boolean duplicate(int numbers[], int length, int[] duplication)
{
    boolean[] k = new boolean[length];
    for (int i = 0; i < k.length; i++)
    {
        if (k[numbers[i]] == true)
        {
            duplication[0] = numbers[i];
            return true;
        }
        k[numbers[i]] = true;
    }
    return false;
}

思路2:

数字在范围0-n-1,那么就能够开辟一个n的状态数组,假如在第i个数字的时候,查看flag[numbers[i]]是否为true,假如是true,那么就表示已经是出现过的。

代码实现:

public boolean duplicate1(int numbers[], int length, int[] duplication)
{
    boolean[] flag = new boolean[length];
    for (int i = 0; i < length; i++)
    {
        if (flag[numbers[i]] == true)
        {
            duplication[0] = numbers[i];
            return true;
        }
        flag[numbers[i]] = true;
    }
    return false;
}

思路3:

hash统计

代码实现:

public boolean duplicate(int numbers[], int length, int[] duplication)
{
    if (length == 0)
        return false;
    HashMap map = new HashMap();
    //hash映射
    for (int i = 0; i < length; i++)
    {
        if (map.containsKey(numbers[i]))
        {
            int temp = map.get(numbers[i]);
            map.put(numbers[i], ++temp);
        }
        else
            map.put(numbers[i], 0);
    }
    //找到第一个重复的 return
    for (int i = 0; i < length; i++)
    {
        if (map.get(numbers[i]) > 0)
        {
            duplication[0] = numbers[i];
            return true;
        }
    } //for
    return false;
}

思路4:

2-bitmap

代码实现:

public boolean duplicate1(int numbers[], int length, int[] duplication)
    {
        //一个Int是4字节 4*8=32位,用2位表示一个数有无重复 00表示没有出现 01 表示出现一次 10表示出现两次
        int arrSize = (int) Math.ceil((double) length / 16); //确定我们需要开辟多少的int空间,16=32(int的位数)/2(2位表示)
        int arr[] = new int[arrSize];
        for (int i = 0; i < length; i++)
        {
            int x = numbers[i];
            int m = x >> 4; //x/16; m表示确定到arr数组中的第几个
            int n = x & 15; //x%16; n表示确定到int中的第几位
            //(arr[m]&(0x3>(2*n) 0x3:二进制表示11,把11左移2*n位;arr[m]&(0x3<<(2*n)):获取两位的值,右移将值取出来
            int cnt = (arr[m] & (0x3 > (2 * n);
                        //如果值小于2,表示要么对应的次数 要么有一次,要么没有
                        if (cnt < 2)
                        {
                            cnt++;
                            //清空对应的值,同时保证其他位上的数字不变(所以要用~)
                            arr[m] &= ~((0x3 << (2 * n)));
                            //赋值相加
                            arr[m] |= cnt << (2 * n);
                        }
                    }
                    //判断重复
                    for (int i = 0; i < length; i++)
                    {
                        int m = numbers[i] >> 4;
                        int n = numbers[i] & 15;
                        if ((arr[m] & (0x3 > (2 * n) == 2)
                                {
                                    duplication[0] = numbers[i];
                                    return true;
                                }
                            }
                            return false;
                        }

以上的4种在数组中找出任意一个重复数字的代码实现和思路大家都了解了吗?可以参考一下,希望能够对大家有所帮助呢。

更多Java实例,请继续来本站了解吧。