算法练习

题目:  1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来;不用辅助存储空间，能否设计一个算法实现?

 1 import java.util.Arrays;
 2 import java.util.Random;
 3 
 4 public class _01唯一成对的数 {
 5     public static void main(String[] args) {
 6         int N = 11;
 7         int[] arr = new int[N];
 8         for (int i = 0; i < arr.length - 1; i++) {
 9             arr[i] = i + 1;
10         }
11         //最后一个数，是随机数
12         arr[arr.length - 1] = new Random().nextInt(N - 1) + 1;
13         //随机下标
14         int index = new Random().nextInt(N);
15         swap(arr, index, arr.length - 1);
16         print(arr);
17     /*
18     采用异或的方法将重复的值找出(不使用辅助空间)*/
19         int x1 = 0;
20         for (int i = 1; i <= N - 1; i++) {
21             x1 = (x1 ^ i);
22         }
23         for (int i = 0; i < N; i++) {
24             x1 = x1 ^ arr[i];
25         }
26         System.out.println(x1);
27 //  使用辅助空间
28         System.out.println("==========");
29         int[] helper = new int[N];
30         for (int i = 0; i < N; i++) {
31             helper[arr[i]]++;   // 将重复的数的重复次数在helper数组里自加
32         }
33         print(helper);
34         for (int i = 0; i < N; i++) {
35             if (helper[i] == 2) {
36                 System.out.println(i);
37                 break;
38             }
39         }
40     }
41 
42     /**
43      * 将数组的两个值交换
44      *
45      * @param arr
46      * @param i
47      * @param j
48      */
49     public static void swap(int[] arr, int i, int j) {
50         int tmp = arr[i];
51         arr[i] = arr[j];
52         arr[j] = tmp;
53     }
54 
55     /**
56      * 打印数组
57      *
58      * @param arr
59      */
60     public static void print(int[] arr) {
61         System.out.println(Arrays.toString(arr));
62     }
63 }

 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　2021-02-15

版权声明：本文为btlord原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/btlord/p/14404139.html