至少在两个数组中出现的值【LC2032】
Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.
我还没阳，坚持住！
哈希表+位运算
2022/12/29
- 思路：使用一个哈希表记录每个数字在三个数组中的出现情况，哈希表的key值为数值大小，value值为该数字在数组中的出现情况，从左到右第i位为1则表示该数字在第i个数组中出现过。最后根据value值将至少出现在两个数组中的num添加至结果集
。如果数字在nums3出现过，那么state大于4证明该数字符合要求
。如果数字在nums3未出现过，那么state大于等于3证明该数字符合要求
- 实现
class Solution { public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) { int MAX = 100; int[] numToState = new int[MAX + 1]; List<Integer> res = new ArrayList<>(); for (int num : nums1){ numToState[num] |= 1; } for (int num : nums2){ numToState[num] |= 1 << 1; } for (int num : nums3){ numToState[num] |= 1 << 2; } for (int i = 0; i <= MAX; i++){ if (((numToState[i] >> 2) & 1) == 1 && numToState[i] > 4){ res.add(i); }else if (((numToState[i] >> 2) & 1) != 1 && numToState[i] >= 3){ res.add(i); } } return res; } }
。复杂度分析
- 时间复杂度：O(n1+n2+n3+C)，遍历三个数组各一次，再遍历哈希表
- 空间复杂度：O(C)，哈希表的大小
- 优化：当value值大于2并且不等于4的时候，就表明key出现了至少两次
class Solution { public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) { int MAX = 100; int[] numToState = new int[MAX + 1]; List<Integer> res = new ArrayList<>(); for (int num : nums1){ numToState[num] |= 1; } for (int num : nums2){ numToState[num] |= 1 << 1; } for (int num : nums3){ numToState[num] |= 1 << 2; } for (int i = 0; i <= MAX; i++){ if (numToState[i] > 2 && numToState[i] != 4){ res.add(i); } } return res; } }
