题解 | #数组中只出现一次的数(其它数出现k次)#
数组中只出现一次的数(其它数出现k次)
http://www.nowcoder.com/practice/5d3d74c3bf7f4e368e03096bb8857871
package org.example.test; import java.util.HashMap; import java.util.Map; public class BitTest { public static void main(String[] args) { int[] nums = {5, 4, 1, 1, 5, 1, 5}; foundOnceNumber1(nums, 3); System.out.println(1 << 5); } /** * 暴力算法 * * @param arr * @param k * @return */ public int foundOnceNumber(int[] arr, int k) { // write code here Map<Integer, Integer> map = new HashMap<>(); for (int value : arr) { if (map.get(value) == null) { map.put(value, 1); } else { map.put(value, map.get(value) + 1); } } for (Integer key : map.keySet()) { if (map.get(key) == 1) { return key; } } return -1; } /** * i * 3 2 1 * 1 0 1 * 1 0 1 * 1 0 1 * 1 0 0 * 0 0 1 * 0 0 1 * 0 0 1 * <p> * i=1: 6%3=0 * i=2: * i=3: 4%3=1 * 如果 == 1, 表示只出现一次的数这个i为是1,遍历32位,结果相加则为只出现一次的数 * * @param arr * @param k * @return */ public static int foundOnceNumber1(int[] arr, int k) { if (arr == null || arr.length <= 0) { return 0; } int result = 0; for (int i = 0; i <= 31; i++) { int curBitCnt = 0; for (int num : arr) { if ((num >> i & 1) != 0) { curBitCnt++; } } if (curBitCnt % k == 1) { result += 1 << i; } } return result; } }
算法 文章被收录于专栏
数据结构和算法