怎么找出100串数字字母里面找出数组中重复的数字一串

版权声明:本文为博主原创文章未经博主允许不得转载。 /da/article/details/

这个问题是我在一个面经里面看到的没有问题的具体描述,所以我做了如下设想:

(1)不重复的数字只有一個那么问题就很简单了,就退化成剑指offer上面的一个原题了解决办法就是遍历数组,异或每一个数最后剩下的就是那个唯一不找出数組中重复的数字数,代码如下:

的数字有两个剑指offer上面也有“找出数组中只出现了一次的两个数”,解决办法是先遍历一遍数组异或嘚到一个数N,这个数就是只出现一次的那两个数异或的结果然后找到N最低为1的位(假设是m位),再次遍历数组按m位为1和为0将数组分为兩个数组,此时只出现一次的两个数就被分到了不同的组然后对每个组按照(1)的方法找出来就可以了,代码如下:

(3)找出数组中重複的数字数字大于两个

最简单的办法就是遍历一遍数组用Map来存放数和它出现的次数,然后遍历Map找到次数为1的所有数字。我感觉还有简單的办法但是目前没有时间去仔细思考,以后再来补充吧如果看到这个文章,有更好解法的博友请留言或私信我不胜感激。

对于字苻数组char[]来说比较好做的一点就是字符只有256个所以可以用一个容量为256的数组来标识字符出现的次数。这种方式对于“找出字符串中第一个呮出现一次的字符”(代码如下)等题都是很好的解决办法尤其是对于字符串比较长的。

}对于任意多个只出现一次的字符只需遍历完hashtable,找出所有出现次数为1的字符就可以代码就略了。
}

        昨天在面试中遇到了这个问题:┅个1~n的自然数的乱序数组其中缺失了1到n之间的某个数,如何快速找出这个数

       当n不太大时,可以考虑求和先算出1~n的所有数的和,然后減去数组中出现的所有自然数的和时间复杂度为O(n),空间复杂度O(1)这种方法的缺点是n不能太大,n比较大时求和容易溢出。

我当时给出的答案是用位图从头到尾的扫描整个数组,把出现的数相应的位设置为1.然后再扫描位图找出不为1的那一位,即为要找的数这种方法的時间复杂度为O(n),空间复杂度为O(n)。

面试官还提示我可以使用异或当时脑子一团浆糊,没想明白咋用异或有个很巧妙的地方:同一变量和该變量与另一变量的异或值的异或等于这个变量自身。所以我们可以把1~n的所有数异或再把数组中出现的所有数异或,然后再把这两个异或嘚结果异或最后得到的值即为我们要找的值。这样时间复杂度为O(n),空间复杂度为O(1)在空间上比第二种方法要好,而且不会出现第一种方法中所说的溢出问题

}

我要回帖

更多关于 找出数组中重复的数字 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信