[算法] 举一反三之n重复数组中找唯一m重复异类数

n重复数组,是指数组中的数字都出现n次;

唯一m重复异类数,是指存在唯一一个没出现n次,只出现了m次的数;

这里我简记它为nX+my问题,求解y,其中m < n,数组中都是整数;

 

3X+y问题

一直没有精力刷leetcode,今天查问题无意中看到了leetcode 137:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次;找出那个只出现了一次的元素。要求时间复杂度O(n),空间复杂度O(1);

没有在第一时间想到思路,于是花时间研究了一下;

这是一个3X+y的问题;先给出最优解:

a, b = 0, 0 for num in nums: a = (a ^ num) & ~b b = (b ^ num) & ~a return a

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpxypz.html