136.只出现一次的数字

136.只出现一次的数字,第1张

136.只出现一次的数字

题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解题思路:首先,HashMap 是我们解决此类问题最先想到的数据结构,由于其 key 值的唯一性,用来解决此类问题再好不过了。题目中已经说了,只会有一个元素出现一次,其余元素均出现两次,那么方法如下:循环遍历该数组,将数组的每个元素作为 key 值 put 到 HashMap 中,每次 put 之前判断一下该 HashMap 中是否包含此 key 值,如果包含,则将此 key-value 键值对移除,如果不包含,则将此 key-value 键值对 put 到 HashMap 中,value 的值可随意设置,因为我们并不会用到此 value 值,只会用到该 value 值对应的 key 值。题目中说明了只会有一个元素出现一次,那么我们遍历数组、 *** 作 HashMap 之后,该 HashMap 的大小一定是 1,所以直接输出 key 值就行,value 的取值并不关心。代码如下:

package leetCode.easy.singleNumber;

import java.util.HashMap;
import java.util.Map;


public class SingleNumber {

    public static Integer singleNumber(Integer[] nums) {
        Map singleNumberMap = new HashMap<>();
        for (int i = 0; i< nums.length; i++) {
            if (singleNumberMap.containsKey(nums[i])) {
                singleNumberMap.remove(nums[i]);
            } else {
                singleNumberMap.put(nums[i], 1);
            }
        }
        for (Integer key : singleNumberMap.keySet()) {
            return key;
        }
        return -1;
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[]{4, 1, 2, 1, 2};
        Integer result = singleNumber(nums);
        System.out.println("result = " + result);
    }

}

还有一种使用排序来解决的,即将数组元素进行从小到大的自然排序,之后遍历,每次遍历的间隔是 2,如果当前元素和后一个元素的值不相等,那么肯定是当前元素只出现了一次,如果数组元素都遍历完了,还没有找到出现一次的元素,那么肯定是最后一个元素出现了一次,直接 return 即可。代码如下:

package leetCode.easy.singleNumber;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


public class SingleNumber {

    public static Integer singleNumber2(Integer[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i< nums.length; i += 2) {
            if (i == nums.length - 1) {
                return nums[i];
            }
            if (!nums[i].equals(nums[i+1])) {
                return nums[i];
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Integer[] nums = new Integer[]{1, 2, 1, 2, 4};
        Integer result = singleNumber2(nums);
        System.out.println("result = " + result);
    }

}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5718215.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存