专栏首页武培轩的专栏剑指Offer-数组中只出现一次的数字

剑指Offer-数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

思路一:

利用HashSet的元素不能重复,如果有重复的元素,则删除重复元素,如果没有则添加,最后剩下的就是只出现一次的元素

思路二:

用HashMap保存数组的值,key为数组值,value为布尔型表示是否有重复

思路三:

两个不相等的元素在位级表示上必定会有一位存在不同。

将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。

diff &= -diff 得到出 diff 最右侧不为 0 的位,也就是不存在重复的两个元素在位级表示上最右侧不同的那一位,利用这一位就可以将两个元素区分开来。

代码实现

package Array;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

/**
 * 数组中只出现一次的数字
 * 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * num1,num2分别为长度为1的数组。传出参数
 * 将num1[0],num2[0]设置为返回结果
 */

public class Solution37 {
    public static void main(String[] args) {
        Solution37 solution37 = new Solution37();
        int[] array = {1, 2, 2, 3, 4, 4};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        solution37.FindNumsAppearOnce_3(array, num1, num2);
        System.out.println(num1[0] + " " + num2[0]);
    }

    /**
     * 位运算 异或
     * 两个不相等的元素在位级表示上必定会有一位存在不同。
     *
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce_3(int[] array, int num1[], int num2[]) {
        int diff = 0;
        for (int num : array) diff ^= num;
        // 得到最右一位
        diff &= -diff;
        for (int num : array) {
            if ((num & diff) == 0) num1[0] ^= num;
            else num2[0] ^= num;
        }
    }


    /**
     * 用HashMap<K,V>保存数组的值,key为数组值,value为布尔型表示是否有重复
     *
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce_2(int[] array, int num1[], int num2[]) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i])) {
                map.put(array[i], true);
            } else {
                map.put(array[i], false);
            }
        }
        int index = 0;//区分是第几个不重复的值
        for (int i = 0; i < array.length; i++) {
            if (map.get(array[i])) {
                index++;
                if (index == 1) {
                    num1[0] = array[i];
                } else {
                    num2[0] = array[i];
                }
            }
        }
    }

    /**
     * 利用HashSet的元素不能重复,如果有重复的元素,则删除重复元素,如果没有则添加,最后剩下的就是只出现一次的元素
     *
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (!set.add(array[i])) {
                set.remove(array[i]);
            }
        }
        Iterator<Integer> iterator = set.iterator();
        num1[0] = iterator.next();
        num2[0] = iterator.next();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 瓜子面经汇总

    HashMap是常用的Java集合之一,是基于哈希表的Map接口的实现。不支持同步和允许null作为key和value。

    武培轩
  • 排序算法-冒泡排序

    算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

    武培轩
  • 猫眼面经汇总

    java.util.Collections 是一个包装类(工具类/帮助类)。它包含有各种有关集合操作的静态多态方法。此类不能实例化,就像一个工具类,用于对集合中...

    武培轩
  • 10:大整数加法

    10:大整数加法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个不超过200位的非负整数的和。 输入有两行,每...

    attack
  • 【动态规划】01背包问题

    前面用动态规划解决了正则表达式的问题,感觉还是不过瘾,总觉得对于动态规划的理解还没有到位,所以趁热打铁,继续研究几个动态规划的经典问题,希望能够借此加深对动态规...

    用户1370629
  • 经典中的经典算法 动态规划(详细解释,从入门到实践,逐步讲解)

    动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

    233333
  • 【动态规划】01背包问题

    前面用动态规划解决了正则表达式的问题,感觉还是不过瘾,总觉得对于动态规划的理解还没有到位,所以趁热打铁,继续研究几个动态规划的经典问题,希望能够借此加深对动态规...

    弗兰克的猫
  • 哈希表问题-LeetCode 146、290、299、300(哈希表,双向链表,最小上升序列)

    运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作:获取数据 get 和 写入数据 put 。

    算法工程师之路
  • 【递归打卡2】求两个有序数组的第K小数

    给定两个有序数组arr1和arr2,已知两个数组的长度分别为 m1 和 m2,求两个数组中的第 K 小数。要求时间复杂度O(log(m1 + m2))。

    帅地
  • System.arraycopy(src, srcPos, dest, destPos, length) 与 Arrays.copyOf(original, newLength)区别

    System.arraycopy(src, srcPos, dest, destPos, length) 与 Arrays.copyOf(original, n...

    用户1148394

扫码关注云+社区

领取腾讯云代金券