给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。 数据范围:数组大小满足 ,数组中每个元素大小满足-笔试面试资料

这是qklbishe.com第19185 篇笔试面试资料
提供答案分析,通过本文《给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。
数据范围:数组大小满足 ,数组中每个元素大小满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。
数据范围:数组大小满足 给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。          数据范围:数组大小满足  ,数组中每个元素大小满足 ,数组中每个元素大小满足 给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。          数据范围:数组大小满足  ,数组中每个元素大小满足
Java

给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。          数据范围:数组大小满足  ,数组中每个元素大小满足 零葬

1.统计词频(面试时别这么干)

统计词频的解法我就不详细说了,一行是可以解决,但这种炫技没有什么意义。笔试的时候因为赶时间,这么干也就罢了,面试这么干绝对没分。
object Solution {     /**     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可     *     *          * @param nums int整型一维数组          * @return int整型     */     def singleNumber(nums: Array[Int]): Int = {         // write code here         nums.map((_, 1)).groupBy(_._1).mapValues(_.size).toArray.sortBy(_._2)(Ordering[Int])(0)._1     } }

2.位运算

这道题在面试时正确的打开方式应该是用位运算,达成时间复杂度O(n),空间复杂度O(1)的成就。对于32位的整型数据,我们先准备一个长度为32的数组t。这里可能有些同学会有疑问,不是说好的空间复杂度O(1)吗?为什么还要开一个辅助数组?此处的数组是32维的固定长度,与数据量n是没有关系的,因此它仍然算是有限的几个变量,空间复杂度仍然算O(1)。

2.1算法流程

  1. 遍历数组,然后将每个数的二进制表达在32个位上的值累加到辅助数组t的相应位置t[i]上。说白了,这一步就是在对整个数组统计每一位上有多少个1。
  2. 接下来我们遍历辅助数组t,如果t[i]不是3的倍数,说明那个出现一次的数在这个i位上肯定是1,否则这一位上肯定是0。通过或运算,在遍历完成后就能够得到那个只出现一次的数。

接下来解释一下原因:

对于某一个i位而言,由于存在n-1个数出现了3次,假设这些出现3次的数中,有一个数在第i位上是1,那么这一位上的1就是3次;如果有多个出现3次的数在第i位上是1,那么这一位上1的个数会以3的幅度自增,但始终都是3的倍数;如果它们之中没有一个数在第i位上是1,那么t[i]=0,仍然满足t[i]%3=0
然后继续考虑只出现了一次的那个数。如果这个数在第i位上为1,那么累加到t[i]上就会导致t[i]%3=1;如果这个只出现一次的数在第i位上为0,无论出现3次的数在该位上是否有为1的情况,总会有t[i]%3=0成立。
因此只要通过计算t[i]%3的值就能够确定那个仅出现一次的数在这一位上是0还是1,从而还原出这个数。
import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param nums int整型一维数组       * @return int整型      */     public int singleNumber (int[] nums) {         // write code here         int[] t = new int[32];         for(int num: nums){             for(int i = 0; i < 32; i++){                 t[i] += (num >> i) & 1;             }         }         int ans = 0;         for(int i = 0; i < 32; i++){             if(t[i] % 3 == 1){                 ans |= (1 << i);             }         }         return ans;     } }

2.2复杂度分析

虽然第1步统计每一位上1的个数时存在双重循环,但内层的循环次数是固定的有限次,因此这一步的时间复杂度是O(n)的。而第2步的或运算也是固定循环32次,时间复杂度是O(1),因此算法整体的时间复杂度是O(n)。

由于只使用了有限的32个变量组成辅助数组,因此额外空间复杂度仍然是O(1)级别。

3.拓展

根据这个解法,这类问题我们可以写出一个通用版本(转自左神的算法课程),假如某个数出现了k次,而其他数出现了m次,需要注意的是:如果0出现了k次,需要特殊处理。
给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。          数据范围:数组大小满足  ,数组中每个元素大小满足
返回-1时是用户输入不合法的情况,可以不用考虑。

今天 11:16:51 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。 数据范围:数组大小满足 ,数组中每个元素大小满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情