SQL进阶技巧:巧用异或运算解决经典换座位问题
目录
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 = 11 ^ 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;
3 小结
本文详细分析了异或预算的法则及其应用,并利用其性质:
从0开始的自然数与1进行按位异或运算能够得到相邻奇偶数的互换
给出了经典SQL问题-换座位问题的一种优雅解法,通过本文我们可以学习到异或运算在解决实际问题中非常有用,同时也可以提高运算的性能【计算机底层的运算】 。
SQL进阶技巧:经典问题题-换座位-CSDN博客
如果您觉得本文还不错,对你有帮助,那么不妨可以关注一下我的数字化建设实践之路专栏,这里的内容会更精彩。
专栏 原价99,现在活动价59.9,按照阶梯式增长,还差5个人上升到69.9,最终恢复到原价。
专栏优势:
(1)一次收费持续更新。
(2)实战中总结的SQL技巧,帮助SQLBOY 在SQL语言上有质的飞越,无论你应对业务难题及面试都会游刃有余【全网唯一讲SQL实战技巧,方法独特】
(3)实战中数仓建模技巧总结,让你认识不一样的数仓。【数据建模+业务建模,不一样的认知体系】(如果只懂数据建模而不懂业务建模,数仓体系认知是不全面的)
(4)数字化建设当中遇到难题解决思路及问题思考。
我的 专栏具体链接如下:
数字化建设通关指南_莫叫石榴姐的博客-CSDN博客
https://blog.csdn.net/godlovedaniel/category_12706766.html