找出唯一成对的数（位运算）

落日映苍穹つ 2023-07-14 08:11 11阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70][]

解题思路：每个元素只能访问一次，所以不能用双重for循环来遍历数组来找相同的数字；不能使用辅助空间，所以不能使用另外开一个数组来将多有数字出现的次数存起来然后再将次数等于2的数字输出来找重复的数字。但是我们可以根据异或运算的性质来做这个题目。任何数与0做异或运算都等于它本身，两个相同的数字做异或运算等于0。所以我们可以将这个含有唯一成对数字的数组与(1^2^3^4^5……^999^1000)做异或运算就相当于1^(1^2^3^4^5……^999^1000)，2^(1^2^3^4^5……^999^1000)，3^(1^2^3^4^5……^999^1000) 这样就可以把成对的消掉，最后只剩下成对的数了。（假设重复的数是k,那么实际上是(1^2^3^4^5……^k^……^999^1000)^1^2^3^4^k^k……^999^1000，因为成对的都消掉了，所以最后只剩下了一个k，k^k^k = 0^k = k)。

import java.util.Random;
    
    public class 唯一成对的数 {
    
    	public static void main(String[] args) {
    		int N = 1001;
    		//生成一个含有从1~1000的数组
    		int[] arr = new int[N];
    		for (int i = 0; i < arr.length-1; i++) {
    			arr[i] = i+1;
    		}
    		//将最后一个数设置为随机数
    		arr[arr.length-1] = new Random().nextInt(N-1)+1;
    		
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    		System.out.println();
    		//进行连续的异或运算
    		int x1 = 0;
    		for (int i = 1; i < N; i++) {
    			x1 ^= i;
    		}
    		//输出连续位运算的结果
    		System.out.print(x1+" ");
    		System.out.println();
    		for (int i = 0; i < N; i++) {
    			x1 = x1^arr[i];
    			System.out.print(x1+" ");
    		}
    		//输出重复的数
    		System.out.println();
    		System.out.println(x1);
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20230529/dbda86271064460aa927b387be3cb0ff.png