ems国际快递查询,位运算经典算法使用,赵薇

频道:趣闻中心 日期: 浏览:283

在之前,给咱们简略解说过什么是位运算,以及位运算的简略使用。特别找来两道经典算法题,给咱们解说下。

下面这是一道经典的面试题:

给定一个非空整数数组,除了某个元素只呈现一次以外,其他每个元素均呈现两次。找出那个只呈现了一次的元素。

这道题假如考虑数组的巨细,又或者是一组亿级以上的数据,处理起来也不是很简略,假如选用位运算的话,会适当简略。

public static int singleNumber(int[] A) { 
int num = 0;
for(int i = 0; i < A.length; i++) {
num ^= A[i];
}
return num;
}

测验代码:

public static void main(String[] args) {
int[] nums = { 11,11,23,45,33,45,33};
System.out.println(singleNumber(nums));
}

控制台输出打印:

23

what?只是五六行代码就处理了咱们的问题?其实,解说起来也很简略:

咱们知道:a^a=0,而 a^0=a,而且位运算是满意交换律的,两两异或得0,终究就只剩余那个仅有呈现的数了。

再看一道相似的:

给定一个非空整数数组,除了某个元素只呈现一次以外,其他每个元素均呈现三。找出那个只呈现了一次的元素。

public static int singleNumber(int[] nums) {
int len = nums.length, result = 0;
for (int i = 0; i < 32; i++) {
int sum = 0;
for (int j = 0; j < len; j++) {
sum += (nums[j] >> i) & 1;
}
System.out.println(sum % 3);
result |= (sum % 3) << i;
}
return result;
}

测验代码:

public static void main(String[] args) {
int[] nums = { 11,11,11,23,45,33,33,45,45,33};
System.out.println(singleNumber(nums));
}

控制台输出打印:

23

这个解说起来也很好了解:在java中,int 整型共有32位,用num[32]存储这n个数据每个二进制位上1呈现的个数,再%3,假如为1,那阐明这一位是要找元素二进制表明中为1 的那一位。每次内部计算出1地点的位数,终究再复原给result。

再看一位大神代码,感觉比上面的更牛逼

public static int singleNumber(int[] A) {
int ones = 0;// 记载只呈现过1次的bits
int twos = 0;// 记载只呈现过2次的bits
int threes;
for (int i = 0; i < A.length; i++) {
int t = A[i];
twos |= ones & t;// 要在更新ones前面更新twos
ones ^= t;
threes = ones & twos;// ones和twos中都为1即呈现了3次
ones &= ~threes;// 抹去呈现了3次的bits
twos &= ~threes;
}
return ones;
}

测验代码:

public static void main(String[] args) {
int[] nums = { 11,11,11,23,45,33,33,45,45,33};
System.out.println(singleNumber(nums));
}

控制台输出打印:

23

也相同能完成相同的作用。可是愈加高效快捷。初看感觉了解起来仍是比较费力的,咱们看看每次ones,twos,threes的成果

ones:11twos:0threes:0
ones:0twos:11threes:0
ones:0twos:0threes:11
ones:23twos:0threes:0
ones:58twos:5threes:0
ones:26twos:36threes:1
ones:27twos:4threes:32
ones:50twos:9threes:4
ones:22twos:32threes:9
ones:23twos:0threes:32

发现没,通过大神的处理,每次循环完毕,ones保存的都是终究一个呈现一次的数据,同理,twos保存的都是终究一个呈现两次次的数据,threes保存的都是终究一个呈现三次的数据,咱们只需要重视ones终究的成果就可以了,信任咱们了解起来也就方便了许多。

java进阶之路,爱好才是咱们最大的导师,求知欲和好奇心会让咱们走的更远。只是会用几个结构,会copy两行代码,永久也无法使自己前进。