算法面试题汇总_1只出现一次的数字

素颜马尾好姑娘i 2021-12-13 02:29 206阅读 0赞

**题目**：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
**说明**：  
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？  
**示例 1**:  
输入: \[2,2,1\]  
输出: 1  
**示例 2**:  
输入: \[4,1,2,1,2\]  
输出: 4

**思路**  
使用hashmap，遍历数组，将数字的值作为键，将数字出现的次数作为值，如果数字没有在hashmap中，添加键值（数字，1）；如果出现过，添加（数字，2），遍历hashmap，找到值为1对应的键。即为答案。

**代码实现**

package 高频题2018.热身.热身;
    
    import java.util.HashMap;
    
    /*
    **题目**：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    **说明**：
    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
    **示例 1**:
    输入: [2,2,1]
    输出: 1
    **示例 2**:
    输入: [4,1,2,1,2]
    输出: 4
     */
    public class 只出现一次的数字 {
        public static void main(String[] args) {
            int[] arr = {2,2,1};
            System.out.println(repeatNum(arr));
        }
        public static int repeatNum(int[] arr){
            //使用hashmap，数字的数值作为键，出现次数作为值
            HashMap<Integer,Integer> kv = new HashMap<>();
            for(int i = 0;i <arr.length;i++){
                if(!kv.containsKey(arr[i])){
                    kv.put(arr[i],1);
                }
                else if(kv.containsKey(arr[i])){
                    kv.put(arr[i],2);
                }
            }
            Integer key = 0;
            //Map,HashMap并没有实现Iteratable接口.不能用于增强for循环.
            for(Integer getKey: kv.keySet()){
                if(kv.get(getKey).equals(1)){
                    key = getKey;
                }
            }
            return key;
    
        }
    }

**结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]

方法二：更简便 异或实现  
**思路**  
异或运算的特点：两个相同的数字异或，结果为0。

因为数组中除了一个元素只出现一次之外，其它的元素都出现两次，如果把所有的数都异或，相同的数字异或为0，最后只剩下出现一次的数字，它和0异或，结果就是它本身。

**代码**

public class 只出现一次的数字 {
        public static void main(String[] args) {
            int[] arr = {2,4,1,1,2};
    //        System.out.println(repeatNum(arr));
            System.out.println(singleNumber(arr));
        }
    
        public static int singleNumber(int[] nums) {
            int num = 0;
            for(int i = 0; i < nums.length; i++){
                num = num ^ nums[i];
            }
            return num;
        }
    }

方法二参考：[https://blog.csdn.net/baidu\_40931662/article/details/83892506][https_blog.csdn.net_baidu_40931662_article_details_83892506]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20211210/b5dba9df90604abf9b1bde310e1b5ee9.png
[https_blog.csdn.net_baidu_40931662_article_details_83892506]: https://blog.csdn.net/baidu_40931662/article/details/83892506