长生的梦呓


  • 归档
  • 算法
  • 基础
  • 关于

  • 分类
  • 日志
  • Servlet
  • Archive
  • 数据结构
  • IO 流

  • 标签
  • 友链
  • MyBatis
  • About
  • Spring 5
  • Java SE
  • Java EE
  • Algorithms
  • 新特性
  • 位运算技巧

  • 搜索
内网穿透 项目实战 数据库 MySQL 安卓踩坑 开发工具 设计模式 Enum 枚举 Linux MyBatis-plus JSON IDEA Transactions AOP IO 流 DP IoC 与 DI 位运算技巧 工具类 学习技巧 Git JDK 排序 Spring Boot Spring MVC Spring Framework MyBatis Log4J Regex Jsoup JDBC 数据结构 递推 递归 算法 Servlet与JSP 小难 中等 简单

【位运算技巧】异或运算符(2)数组中找出唯一重复的数

发表于 2020-04-03 | 1 | 阅读次数 305

前言

位运算 异或(^)蛮有意思的,分享一下。

一、题目

1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。

每个数组元素只能访问一次,设计一个算法,将它找出来。

不用辅助存储空间,能否设计一个算法实现?

提示:异或( ^ )可以去除两个重复的值。

二、题解

1.奇巧淫技

利用异或( ) 可以去重这一特点。a异或a等于0,a异或0等于a(101异或101等于0)例如,A A B C C等于B,因为AA等于0,消除重复了。

解释:

先将 1 -1000的每一个数都 异或( ^ ) 一次。如果此时再将1-1000异或一次,那么值则为0了。

因为在数值中,有1001个数,中间有两个数是相同的。因为第一个for循环 异或 了1-1000,此时再次for循环遍历数组中所有数,同时 异或 所有数,那么重复的那个数字将会被保留下来,所以那个数字即为重复的数。(两个for循环中,重复的数字一共出现了3次,其他数只出现了两次)

使用异或^。时间复杂度为O(n)。

    public static int solution(int[] arr) {
        int x = 0;
        // 先将1-1000异或一次,1^2^3^...^1000。
        for (int i = 1; i <= 1000; i++) {
            x = x ^ i;
        }
        // 再将1-1000异或一次,但是这里包含了一个重复的数(这个重复的数总共会被异或^三次,从而保留下来)。
        for (int i = 0; i < arr.length; i++) { 
            x = x ^ arr[i];
        }
        return x;
    }

测试数据main方法

	public static void main(String[] args) {
        // 随便生成的测试数据(数据可能是乱序的,我这里只是为了方便)
        int[] arr = new int[1001]; 
        for (int i = 0; i < 1000; i++) {
            arr[i] = i + 1;
        }
        arr[1000] = (int)(Math.random() * (1000+1-1))+1; // 随机生成[1-1000]内的数

		// 测试
        System.out.print(solution(arr));
    }

2.其他解法

使用辅助空间

新建了一个HashSet。使用 Set 不能添加重复的特点,如果找到重复的了就返回那个值。

    public static int solution2(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            boolean add = set.add(arr[i]);
            if (!add) {
                return arr[i];
            }
        }
        throw new IllegalArgumentException("数组中没有两个相同的数!");
    }

新建了一个数组。因为值的范围在 1-1000,所以用值来作为新数组的下标,将值+1。

第二个for循环遍历,找出被值为2的下标,即重复出现的数。

    public static int solution3(int[] arr) {
        int[] newArr = new int[1001];
        for (int i = 0; i < arr.length; i++) {
            int value = arr[i];
            newArr[value]++;
        }
        for (int i = 0; i < newArr.length; i++) {
            if (newArr[i] == 2) {
                return i;
            }
        }
        throw new IllegalArgumentException("数组中没有两个相同的数!");
    }
不使用辅助空间

暴力破解。时间复杂度有点高,为O(n2)

每找一个数时,判断这个数在数组中是否存在,存在则直接返回。

    public static int solution4(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    return arr[i];
                }
            }
        }
        throw new IllegalArgumentException("数组中没有两个相同的数!");
    }

  • 本文作者: 长生的梦呓
  • 本文链接: https://shengjava.com/archives/位运算技巧异或运算符2数组中找出唯一重复的数
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 内网穿透 # 项目实战 # 数据库 # MySQL # 安卓踩坑 # 开发工具 # 设计模式 # Enum # 枚举 # Linux # MyBatis-plus # JSON # IDEA # Transactions # AOP # IO 流 # DP # IoC 与 DI # 位运算技巧 # 工具类 # 学习技巧 # Git # JDK # 排序 # Spring Boot # Spring MVC # Spring Framework # MyBatis # Log4J # Regex # Jsoup # JDBC # 数据结构 # 递推 # 递归 # 算法 # Servlet与JSP # 小难 # 中等 # 简单
【位运算技巧】异或运算符(1)找出落单的数
【Spring】(1)Spring 简单介绍
  • 文章目录
  • 站点概览
长生的梦呓

长生的梦呓

110 日志
39 分类
40 标签
RSS
E-mail CSDN
Creative Commons
Links
  • CSDN 地址
  • waltz26
  • Ryan Wang's Blog
  • JohnNiang's Blog
  • 廖雪峰
  • 菜鸟教程
© 2021 长生的梦呓
浙ICP备20005262号-1