题目描述:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 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) { MapsingleNumberMap = 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); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)