当前位置：首页 > article >正文

SQL进阶技巧：巧用异或运算解决经典换座位问题

article 2024/10/28 10:48:05

0 问题描述

1 数据准备

2 问题分析

2.1 什么是异或

2.2异或有什么特性？

2.3 异或应用

2.4 本问题采用异或SQL解决方案

3 小结

0 问题描述

表 seat中有2个字段id和student

id 是该表的主键（唯一值）列,student表示学生姓名。

该表的每一行都表示学生的姓名和 ID。

id 是一个连续的增量。

编写解决方案来交换每两个连续的学生的座位号。如果学生的数量是奇数，则最后一个学生的id不交换。

按 id 升序返回结果表。

查询结果格式如下所示。

示例 1:

输入:

Seat 表:

输出

注意，如果学生人数为奇数，则不需要更换最后一名学生的座位。

1 数据准备

 create table seat as 
 (
 
     select 
	       stack(
		   
		         5,'a',
				 1,'b',
				 2,'c',
				 3,'d',
				 4,'e',
				 5,'f'   
	   		   
		   )
 )

2 问题分析

2.1 什么是异或

在逻辑学中，逻辑算符异或（exclusive or）是对两个运算元的一种逻辑析取类型，符号为 XOR 或 EOR 或 ⊕（编程语言中常用^）。但与一般的逻辑或不同，异或算符的值为真仅当两个运算元中恰有一个的值为真，而另外一个的值为非真。转化为命题，就是：“两者的值不同。”或“有且仅有一个为真。”

定义

1 ⊕ 1 = 0

0 ⊕ 0 = 0

1 ⊕ 0 = 1

0 ⊕ 1 = 1

总结：相同为0，不同为1

2.2异或有什么特性？

根据定义我们很容易获得异或两个特性：

恒等律： X ⊕ 0 = X

归零律： X ⊕ X = 0

交换律：A ⊕ B = B ⊕ A

结合律：A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C

自反：A ⊕ B ⊕ B = A ⊕ 0 = A

2.3 异或应用

（1）快速比较两个值

先让我们来一个简单的问题；判断两个int数字a，b是否相等，你肯定会想到判断a - b == 0，但是如果判断a ^ b == 0效率将会更高。

（2）使用异或来使某些特定的位翻转，因为不管是0或者是1与1做异或将得到原值的相反值；

0 ^ 1 = 1

1 ^ 1 = 0

例如：翻转10100001的第6位，答案：可以将该数与00100000进行按位异或运算;10100001 ^ 00100000 = 10000001

（3）使用异或来判断一个二进制数中1的数量是奇数还是偶数

例如：求10100001中1的数量是奇数还是偶数；答案：1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1，结果为0就是偶数个1；应用：这条性质可用于奇偶校验（Parity Check），比如在串口通信过程中，每个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位粗略地判断接收到的数据是否有误

（4）校验和恢复

校验和恢复主要利用的了异或的特性：IF a ^ b = c THEN a ^ c = b 应用：一个很好的应用实例是RAID5，使用3块磁盘（A、B、C）组成RAID5阵列，当用户写数据时，将数据分成两部分，分别写到磁盘A和磁盘B，A ^ B的结果写到磁盘C；当读取A的数据时，通过B ^ C可以对A的数据做校验，当A盘出错时，通过B ^ C也可以恢复A盘的数据。

（5）经典题目：不使用其他空间，交换两个值

a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;

原理：
第一步：a = a^b
第二步：b=b^a ,也就是 b=b^a^b ,也就是b=a^0,此处换值
第三步：a=a^b 也就是a=a^b^a,也就是b

（6）最最常出现的面试题：一个整型数组里除了N个数字之外，其他的数字都出现了两次，找出这N个数字；

比如，从{1, 2, 3, 4, 5, 3, 2, 4, 5}中找出单个的数字： 1

让我们从最简单的，找一个数字开始；

题目：（LeetCode 中通过率最高的一道题） Single Number: Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 思路：拿到这个题目，本能的你会使用排序（数字文字我们常常需要排序），排序后可以来判断是否数字成对出现，思路很明显，但是排序的算法上限是 O(nlogn)，不符合题目要求；

学习了强大的异或，我们可以轻松的使用它的特性来完成这道题目：
（1）A ^ A = 0;
（2）异或满足交换律、结合律；所有假设有数组：A B C B C D A使用异或：

A ^ B ^ C ^ B ^ C ^ D ^ A
= A ^ A ^ B ^ B ^ C ^ C ^ D
= 0 ^ 0 ^ 0 ^ D
= 0 ^ D
= D

代码：

class Solution {
public:
	int singleNumber(int A[], int n) {
		//特殊情况1,2
		if(n<=0) return -1;
		if(n==1) return A[0];
		int result = 0;
		for (int i = 0; i < n; i ++) {
			result = result ^ A[i];
		}
		return result;
	}
};

2.4 本问题采用异或SQL解决方案

利用异或的性质，我们可以得到如下结论

从0开始的自然数与1进行按位异或运算能够得到相邻奇偶数的互换

推到：

如2的二进制是10，1的二进制为01，2^1，得到二进制数11，即3，

同理3的二进制是11，1的二进制为01，3^1，得到二进制数10，即2，

所以4（100）-5（101），5（101）-4（100），依次类推。

因此最终的SQL如下：

经典及优雅解法

select rank() over(order by (id-1)^1) as id  ,student from seat

通过异或运算可以看出求解本文的问题就会变得非常简单。

正常解法思路：

select id
     --  , student
     , case when mod(id, 2) = 1 then nvl(lead, student) else lag end student
from (select id
           , student
           , lag(student, 1) over (order by id)  lag
           , lead(student, 1) over (order by id) lead
      from seat) t;