[LeetCode热门100题]|137，260，268，面试17.19

1、137 只出现一次数字||

        1、题目描述

137 只出现一次数字||

https://leetcode.cn/problems/single-number-ii/description/
给你一个整数数组 nums ，除某个元素仅出现 一次 外，别的每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来办理此问题。
 

        2、算法思路

        

，全部我们只需要给一个32的空间，而且用一个表示符号位就可以。
        而且统计每个位置上的1是否是3的倍数，不是的话那个 i 位置上就是1
        用a表示a第i个位置的元素，n=nums.length-1,x表示有n个数的第i个位置是上1

i	total		结果
31	3n个0+a	%3	a
30	3x个1+a	%3	a
........	3(n-x)个0+3x个1+a	%3	a
0	3(n-x)个0+3x个1+a	%3	a[i

        3、算法代码

1. class Solution {
2.     public int singleNumber(int[] nums) {
3.         int ans = 0;
4.         for(int i=0;i<32;++i){
5.             int total = 0;
6.             for(int num:nums){
7.                 total +=((num >>i) &1);
8.             }
9.             if(total % 3 != 0){
10.                 ans |= (1 <<i);
11.             }
12.         }
13.         return ans;
14.     }
15. }

复制代码

        4、结果运行

2、260只出现一次数字|||

        1、题目描述

260. 只出现一次的数字 III - 力扣（LeetCode）

https://leetcode.cn/problems/single-number-iii/description/
给你一个整数数组 nums，其中恰好有两个元素只出现一次，别的全部元素均出现两次。 找出只出现一次的那两个元素。你可以按 恣意顺序 返答复案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来办理此问题。

        2、算法思路

• 先得出a^b=temp
  
• temp不大概是0，全部肯定a和b是最少有一个地方不一样，由于是异或，全部temp出现1的地方就是a和b的差别
  
• 找出第temp数的第diff个位置是1的地方，就可以知道a和b的第diff个位置的元素不一样，肯定是一个diff位置是0，另一个就是1
  
• 把数组中的元素的第diff位置为1的地方放在ret[1],而且给他们异或，由于有2个相同的元素可以刚刚好消除掉，剩下的放入ret[0]也是进行异或操纵
  

        3、算法代码

1. class Solution {
2.         public static int[] singleNumber(int[] nums) {
3.         //1、先把所有的数字异或在一起，然后得出 a^b=temp
4.         int temp = 0;
5.         for (int x:nums) temp ^= x;
6.         //找出temp一个位置是1的地方
7.         int diff = 0;
8.         while (true){
9.             if (((temp >> diff) & 1)==1) break;
10.             else diff++;
11.         }
12.         //然后把第diff位的为1的放在一个ret[1],第diff位置为0反在ret[0]然后全部都异或剩下的就是需要返回
13.         int[] ret = new int[2];
14.         for (int x:nums){
15.             if (((x >> diff)&1)==1)ret[1] ^=x;
16.             else ret[0] ^=x;
17.         }
18.        return ret;
21.     }
22. }

复制代码

        4、结果运行

3、268丢失的数字

可以看我的这篇文章
力扣热门100题【面试题01.01，268】-CSDN博客

https://blog.csdn.net/EdgeAI/article/details/146182204?spm=1001.2014.3001.5501
        1、题目描述

268. 丢失的数字 - 力扣（LeetCode）

https://leetcode.cn/problems/missing-number/description/给定一个包罗 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

        2、算法代码

1. class Solution {
2.     public int missingNumber(int[] nums) {
3.         int ret = 0;
4.         for(int x:nums) ret ^=x;
5.         for(int i=0;i<=nums.length;i++)ret ^=i;
6.         return ret;
7.     }
8. }

复制代码

        3、结果运行

4、面试17.19消散的两个个数字（结合260和268）

这道题目结合260和268一起做很更加简单，这就是为什么我把它放在最后。
        1、题目描述


        2、算法思路

• 找出缺少的两个数字等到他们的异或
  
• 找出他们异或的位置不一样的位置，可以是任何地方位置是1的地方，为了方便我就寻找右边第一个是1的位置
  
• 而且按照题目260，只出现一次的数字||| 把他们的第diff个位置为0的异或以后放在ret[0],第diff个位置为1的异或以后放在ret[1]
  
• 这个时候数字还没有抵消由于没有一样的，所以这个时候我们遍历1 到 N 全部的整数就可以抵消掉
  

        3、算法代码

1. class Solution {
2.     public int[] missingTwo(int[] nums) {
3.         //先把缺少的2个数字找出来
4.         int temp = 0;
5.         for(int x:nums) temp ^=x;
6.         for(int i=1;i<=nums.length+2;i++) temp ^=i;
8.         //目前的temp中有缺少的2个数字的异或
9.         //先找出从右往左 找出temp的第一个1
10.         int diff = 0;
11.         while(true){
12.             if(((temp >> diff)&1)==1) break;
13.             else diff++;
14.         }
16.         //按照 diff 位置的不同 把第diff位置为0的分成一部分，为1的分成一部分
17.         int[] ret = new int[2];
18.          for(int n : nums){
19.             if(((n >> diff) & 1) == 1) ret[1] ^= n;
20.             else ret[0] ^= n;
21.          }
22.         for(int i = 1; i <= nums.length + 2; i++){
23.             if(((i >> diff) & 1) == 1) ret[1] ^= i;
24.             else ret[0] ^= i;
25.         }
26.         return ret;
27.     }
28. }

复制代码

        4、结果运行

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。