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

﹏ヽ暗。殇╰゛Y 2022-11-27 03:10 132阅读 0赞

#### 问题 ####

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

#### 分析 ####

在位运算中，A ^ A = 0; B ^ 0 = B，我们可以让1—1000这1000个数异或后的值跟数组中的1001个元素异或，即（1 ^ 2 ^ … ^ 1000）^（1 ^ 2 ^ … ^ 1000 ^ 重复数k），即（1 ^ 1） ^ （2 ^ 2） ^ … ^ （1000 ^ 1000） ^ 重复数k，这样前1—1000分别和后面1—1000两两异或，最终为 0 ^ 重复数k，最终得到重复数k。

#### 代码实现 ####

import java.util.Random;
    
    public class _01找出唯一成对的数 { 
    	public static void main(String[] args) { 
    		int N = 1001;
    		int []arr = new int[N];
    		//产生1-1000这1000个数
    		for(int i = 0;i<arr.length-1;i++) { 
    			arr[i] = i+1;
    		}
    		
    		//随机下标
    		int index = new Random().nextInt(N);
    		arr[arr.length - 1] = arr[index];
    		
    		//产生1-1000中的随机数
    		arr[index] = new Random().nextInt(N-1)+1;
    		
    		int x1 = 0;
    		//1^2……^1000
    		for(int i = 1;i<=N-1;i++) { 
    			x1 = (x1^i);
    		}
    		
    		//根据 A ^ A = 0; B ^ 0 = B
    		//x1 = 1^2 ^……^ 1000 ^ 1^2 ^……^ 1000 ^ 随机数 = 0 ^ 随机数 = 随机数
    		for(int i = 0;i<N;i++) { 
    			x1 = x1^arr[i];
    		}
    		System.out.println(x1);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关找出水仙花数

1 问题水仙花数是指一个3位数，它的每位上的数字的三次幂之和等于它本身，那么如何求出所有水仙花数呢？ 2 方法 <table> <tbody> <tr>

- 日理万妓/ 2024年03月31日 11:14/ 0 赞/ 83 阅读

相关 Pintia题解——7-13 找出三位水仙花数

目录 7-13 找出三位水仙花数原题：解题思路： JavaScript(node)代码：复杂度分析：

迈不过友情╰/ 2024年02月26日 07:41/ 0 赞/ 66 阅读

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

题目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L

落日映苍穹つ/ 2023年07月14日 08:11/ 0 赞/ 12 阅读

相关位运算（2）——找出唯一成对的数

问题 1—1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来。不用辅

﹏ヽ暗。殇╰゛Y/ 2022年11月27日 03:10/ 0 赞/ 133 阅读

相关 693 交替位二进制数（位运算）

1. 问题描述：给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。示例 1：输入：n = 5 输出

雨点打透心脏的1/2处/ 2022年09月03日 10:19/ 0 赞/ 172 阅读

相关编程找出不同的四位平方数对,它们由相同的数字构成

问题重述： \[ 1024,2401; 1089,9801; 1296,2916; 1296,9216; 1369,1936; 1764,4761; 2916,9216; 4

缺乏、安全感/ 2022年08月07日 04:50/ 0 赞/ 97 阅读

相关水仙花数的找出

//水仙花数是指一个3位数，其各位数字立方和等于其本身。书本p81,19 \include <iostream> using namespace std; //标准命名

今天药忘吃喽~/ 2022年06月07日 10:50/ 0 赞/ 210 阅读

相关编程实现找成对数中唯一的单独数

编程实现：一组数据中只有一个数字出现了一次。其他所有数字都是成对出现的。请找出这个数字。（使用位运算） include<stdio.h> inc

「爱情、让人受尽委屈。」/ 2022年05月27日 03:42/ 0 赞/ 109 阅读

相关找出不存在的两位数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmdo

不念不忘少年蓝@/ 2022年01月23日 11:01/ 0 赞/ 207 阅读

相关算法19-----（位运算）找出数组中出现只出现一次的数

题目：前三题都可以用集合和来求。【sum(set(nums)）*N-sum(nums)】 1、数组中别的数都出现2次，只有一个数出现1次，找出该数。 2、数组中别的...

系统管理员/ 2021年03月28日 14:40/ 0 赞/ 434 阅读