OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!)

2024-02-04 14:36

本文主要是介绍OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.单身狗1

1.1 题目描述

1.2排序寻找

1.3巧用位操作符

2.单身狗2

1.1 题目描述

1.2排序寻找

1.3巧用位操作符


                           不是每个人都能做自己想做的事,成为自己想成为的人。

                                                  克心守己,律己则安!

创作不易,宝子们!如果这篇文章对你们有帮助的话,别忘了给个免费的赞哟~ 

1.单身狗1

1.1 题目描述

在一个整型数组中,只有一个数字出现一次,其他数组都是成对出现的,请找出那个只出现一次的数字。

例如:

数组中有:1 2 3 4 5 1 2 3 4,只有5出现一次,其他数字都出现2次,出5

1.2排序寻找

1. 对于一个无序的数组,当我们将他们进行排序后,一切问题都会简单很多的~

冒泡排序的伪代码~

void sort(int arr[], int len)
{int i = 0;int j = 0;for (i = 0; i < len - 1; i++){int flag = 1;for (j = 0; j < len - 1; j++){if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;}}if (flag == 1)break;}//冒泡排序-》升序数组
}

2. 那我们要如何找到那个“单身狗”呢~

我们可以很容易的注意到相邻的2个元素是相同的,那我们是不是可以俩俩比较呢,若不同,则前面的那个元素一定就是“单身狗”啦~

下面是这部分的伪代码~

for (i = 0; i < len; i+=2)
{if (arr[i] != arr[i + 1]){printf("单身狗数字是:%d\n", arr[i]);break;}
}

3. 不过,我们还要考虑边界情况呢~

当我们将前面的元素都比较完后,还没有找到单身狗,而按照上面的算法逻辑的话,最后那个元素是无法俩俩比较的,那我们该怎么办呢~

我们不妨立个flag=1;若在上面的逻辑中找到单身狗,flag=0,若没有找到,flag还是=1,

那单身狗就是最后那个元素啦~

int flag = 1;
for (i = 0; i < len; i+=2)
{if (arr[i] != arr[i + 1]){printf("单身狗数字是:%d\n", arr[i]);flag = 0;break;}
}
if (flag == 1)printf("单身狗数字是:%d\n", arr[len-1]);

1.3巧用位操作符

1. 这个题目其实还有更为巧妙的方法呢~

这里先给俩个结论1.相同的俩个元素^(抑或)结果为零~

                                 2.零与其他元素抑或结果为那个元素本身~

那是为什么呢~(其实在我之前的博客也提到过,这里再说明一下)http://【有趣的移位操作符和位操作符(由浅入深轻松搞定!) - CSDN App】http://t.csdnimg.cn/q2ubr

2. 好了,知道了这些那这个题目就显得异常简单了啦~

我们将所有元素抑或起来是不是就找到了那个单身狗呢~

下面是这部分的伪代码~

int find_single_dog(int arr[], int sz)
{int ret = 0;int i = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}return ret;
}//sz是数组的长度

2.单身狗2

1.1 题目描述

一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如:

有数组的元素是:1,2,3,4,5,1,2,3,4,6

只有5和6只出现1次,要找出5和6.

1.2排序寻找

1.这个题目如果用排序来做的话,主要的算法部分其实和前面的是差不多的~

唯一不同的是我们要找的俩个“单身狗”后才能结束寻找~

我们可以用count来计数,当count==2时,就结束寻找~

代码如下~

for (i = 0; i < len-1; i+=2)
{if (arr[i] != arr[i + 1]){printf("单身狗是%d\n", arr[i]);count++;i--;}if (count == 2)break;
}

2. 当然我们还要考虑边界情况的~

我们可以很容易的知道上面的代码逻辑一定可以至少找到一个单身狗5

当循环结束后i是等于len-1的,所以优化后的代码如下~

	for (i = 0; i < len-1; i+=2){if (arr[i] != arr[i + 1]){printf("单身狗是%d\n", arr[i]);count++;i--;}if (count == 2)break;}if(i==len-1)printf("单身狗是%d\n", arr[i]);//考虑边界情况
}

1.3巧用位操作符

1. 上面的代码还是不够牛逼,让我们看看牛逼的代码~

当单身狗只有一个时,我们可以用位操作的方法快速找到,这里有俩个不同的元素,这时我们就不可以简单的将他们全部抑或起来了,那怎么办呢~

2. 我们可不可以想办法将这俩个单身狗分开来后再进行抑或呢~(举个栗子,数据不一定正确分配)

3. 我们先将所有元素抑或起来(还是以上面的元素为例~)

然后我们将结果放到临时变量tmp中,那tmp到底有什么用呢~

我们仔细思考一下就会惊奇的发现(找到tmp二进制中第一个1(相异为1)可以区分俩个不同的单身狗!)即:找到有分歧的一位。在这一位上,两个数一定是一个1一个0

找tmp二进制中的第一个1的代码如下~

//找到tmp二进制中第一个1(相异为1)区分俩个不同的元素
int count = 0;//用count来记录tmp二进制中的第一个1
while ((tmp & (1<<count))==0)
{count++;
}

4. 最后,我们要将数组中的所有元素右移count位后再与一按位与(此时一定可以将不同的单身狗区分开来,至于其他相同的元素不管他们那一位上是1还是0都会被分配到相同的部分

//数组中的元素右移count后&1
for (int i = 0; i < len; i++)
{if (((arr[i] >>= count) & 1) == 1)*tmp1^= arr[i];else*tmp2^= arr[i];
}

注:tmp1和tmp2一定要初始化为零呢~,还要注意运算符的优先级(一定要加括号按照我们的思路计算!)

附:完整的代码~

void Fun(int arr[], int*tmp1, int*tmp2, int len)
{int tmp = 0;//将所有元素抑或起来结果放到tmp中for (int i = 0; i < len; i++)tmp ^= arr[i];//找到tmp二进制中第一个1(相异为1)区分俩个不同的元素int count = 0;//用count来记录tmp二进制中的第一个1while ((tmp & (1<<count))==0){count++;}//数组中的元素右移count后&1for (int i = 0; i < len; i++){if (((arr[i] >>= count) & 1) == 1)*tmp1^= arr[i];else*tmp2^= arr[i];}
}

5.完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

 

这篇关于OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677832

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Centos环境下Tomcat虚拟主机配置详细教程

《Centos环境下Tomcat虚拟主机配置详细教程》这篇文章主要讲的是在CentOS系统上,如何一步步配置Tomcat的虚拟主机,内容很简单,从目录准备到配置文件修改,再到重启和测试,手把手带你搞定... 目录1. 准备虚拟主机的目录和内容创建目录添加测试文件2. 修改 Tomcat 的 server.X

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring Boot拦截器Interceptor与过滤器Filter详细教程(示例详解)

《SpringBoot拦截器Interceptor与过滤器Filter详细教程(示例详解)》本文详细介绍了SpringBoot中的拦截器(Interceptor)和过滤器(Filter),包括它们的... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)详细教程1. 概述1