剑指OfferJZ50：数组中重复的数字-java版

缺乏、安全感 2022-08-30 05:15 93阅读 0赞

### 剑指OfferJZ50：数组中重复的数字-java版 ###

*   *   *  JZ50:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组\[2,3,1,0,2,5,3\]，那么对应的输出是2或者3。存在不合法的输入的话输出-1‘’

### JZ50:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组\[2,3,1,0,2,5,3\]，那么对应的输出是2或者3。存在不合法的输入的话输出-1‘’ ###

**维护当前数组下标index和其对应的值a\[index\]相等 如：a\[index\]=index（ 这种情况说明当前值的出现次数不少于1次）  
通过维护这种关系找到数组中重复的数字**  
具体步骤：

*  当前数组下标index和其对应的值a\[index\]相等，不需要维护（关系）当前数组下标index和其对应值相等
 *  当前数组下标index和其对应的值a\[index\]不相等，便将a\[index\]与a\[a\[index\]\]交换，维护关系
 *  当前数组下标index和其对应的值a\[index\]不相等，如果a\[a\[index\]\]已经维护过了，维护结束，返回当前下标所对应的值

如图：a\[0\]=2 下标0!=2 便将a\[0\]与a\[2\]对应的数值交换，维护关系  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

继续往下走，a\[1\]=3 下标1!=3 便将a\[1\]与a\[3\]对应的数值交换，维护关系  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

继续往下走，a\[2\]=2 下标2!=2，满足关系  
继续往下走，a\[3\]=3 下标3!=3 ，满足关系  
继续往下走，a\[4\]=2下标4!=2 ，由于a\[2\]已经维护过了，维护结束，返回当前下标4所对应的值a\[4\]

public class jz50{ 
        public static int duplicate (int[] numbers) { 
            // write code here
            int ans=-1;
            for(int i=0;i<numbers.length;i++) { 
                //当前数组下标index和其对应的值a[index]相等
                if (numbers[i] == i) { 
                    continue;//不需要维护（关系）当前数组下标index和其对应值相等
                }
                //当前数组下标index和其对应的值a[index]不相等
                //如果a[a[index]]已经维护过了，维护结束，返回当前下标所对应的值
                if (numbers[numbers[i]] == numbers[i]) { 
                    ans = numbers[i];
                    break;
                }
                //当前数组下标index和其对应的值a[index]不相等
                //便将a[index]与a[a[index]]交换，维护关系
                int temp = numbers[i];
                numbers[i] = numbers[numbers[i]];
                numbers[temp] = temp;
            }
            return ans;
        }
        //测试
        public static void main(String[] args) { 
            int[] a=new int[]{ 2,3,1,0,2,5,3};
            duplicate(a);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][2021071911503760.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20220829/655902cc64b44138bf4bc0b4fa0b51e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/a8dd798b052446e896b5e37f476b8833.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/6f8dcb88a19d4f9bbdb8236414302eba.png
[2021071911503760.gif_pic_center]: /images/20220829/7feabe554c754c6a9c707a9eec11e339.png