剑指offer练习日志01--数组小练习

这篇具有很好参考价值的文章主要介绍了剑指offer练习日志01--数组小练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

剑指offer练习日志01--数组小练习

目录

一.剑指 Offer 03. 数组中重复的数字(原地哈希思想)

问题描述:

问题分析:

原地哈希思想排序:

题解算法gif: 

算法接口:

二.二维数组中的查找(😍行列交叉二分法😍)

问题描述:

方法一:🤔对角元素比较搜索法🤔

算法思想:

算法gif: 

算法接口实现:

方法二.😍行列交叉二分法😍

基本思想介绍:

算法实现:


一.剑指 Offer 03. 数组中重复的数字(原地哈希思想)

剑指 Offer 03. 数组中重复的数字 - 力扣(Leetcode)https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

问题描述:

  • 🤪在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。🤪

示例 :

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3 

问题分析:

  • 🤪问题中数组长度为n,且其中的元素的值被限制在了 0 ~ n-1的范围内,因此我们将数组的每一个元素m都交换到数组下标为m的位置上(类似于鸽巢思想)(数组下标与元素值建立绝对映射),通过这种方式可以完成时间复杂度为O(N),空间复杂度为O(1)的哈希思想排序,在排序的过程中可以加上简单的重复数字判断语句便可以完成本题的求解.🤪剑指offer练习日志01--数组小练习

原地哈希思想排序:

剑指offer练习日志01--数组小练习

题解算法gif: 

剑指offer练习日志01--数组小练习

算法接口:

class Solution 
{
public:
    int findRepeatNumber(vector<int>& nums) 
    {
        int size = nums.size();
        int ptr = 0;           //用于遍历数组(相当于算法描述中的下标i)
        while(ptr<size) 
        {   
            int m = nums[ptr];
            if(m==ptr)         //判断元素的值和其下标是否相同(相同则表明元素已经归位)
            {
                ++ptr;
            }
            else
            {
                while(m != ptr)    //内层循环
                {
                    if(m==nums[m]) //判断元素是否重复
                    {
                        return m;  
                    }
                    swap(nums[ptr],nums[m]);  //令m元素归位
                    m=nums[ptr];              //更新m元素,继续完成其余元素的归位
                }
            }
        }
        return false;
    }
};

剑指offer练习日志01--数组小练习

  • 😃算法中每个元素只需完成一次归位,因此算法的时间复杂度为O(N)
  • 😃算法的空间复杂度为O(1) 

二.二维数组中的查找(😍行列交叉二分法😍)

剑指 Offer 04. 二维数组中的查找 - 力扣(Leetcode)https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

问题描述:

  • 😝在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入如前所述的一个二维数组和一个整数target,判断数组中是否含有target

😜示例:

😜现有矩阵 matrix 如下:

  [1,   4,  7, 11, 15]
  [2,   5,  8, 12, 19]
  [3,   6,  9, 16, 22]
  [10, 13, 14, 17, 24]
  [18, 21, 23, 26, 30]
  • 😜给定 target = 5,返回 true
  • 😜给定 target = 20,返回 false

方法一:🤔对角元素比较搜索法🤔

算法思想:

🧐待查找矩阵的行数为Row,列数为Col

🧐矩阵首元素的坐标为(0,0)

  • 🧐选取右上角(或者左下角)元素为key元素
  • 🧐key元素具有如下特征:
  1. 😀key是其所在行最大元素
  2. 😀key是其所在列最小元素剑指offer练习日志01--数组小练习
  •  😀每一个查找过程的子步骤中,将target与key进行比较,根据比较结果可以分为三种情况:剑指offer练习日志01--数组小练习
  • 😀假设key元素的坐标为(x,y)(第x列,第y行),则我们的查找范围列坐标范围为[0,x],查找范围行坐标范围为[y,Col-1],即我们取以key为右上对角元素的矩阵每个子步骤中待搜索矩阵,于是通过改变(x,y)坐标就可以实现查找范围的缩小:剑指offer练习日志01--数组小练习
  • 😀可知,每一次单趟查找我们就可以排除当前待搜索矩阵一行元素一列元素,因此该查找算法的时间复杂度为O(Row + Col).

算法gif: 

剑指offer练习日志01--数组小练习

算法接口实现:

class Solution 
{
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) 
    {
        int height= matrix.size();
        if(height == 0)
        {
            return false;
        }
        int lenth = matrix[0].size();
        int x = lenth-1;  //初始右上角元素横坐标
        int y = 0;        //初始右上角元素纵坐标
        while(x>=0 && y<=height-1)  //当x和y其中一个坐标越界时说明target不在矩阵中
        {
            int key = matrix[y][x];
            if(key == target)
            {
                return true;
            }
            else if(key>target)  //可以排除key所在一列元素
            {
                --x;
            }
            else                 //可以排除key所在一行元素
            {
                ++y;
            }
        }
        return false;            //x或y有一个越界说明target不存在
    }
};
  • 注意循环结束的边界条件

剑指offer练习日志01--数组小练习

方法二.😍行列交叉二分法😍

基本思想介绍:

🧐待查找矩阵的行数为Row,列数为Col

🧐矩阵首元素的坐标为(0,0)

剑指offer练习日志01--数组小练习

  • 😃如上图所示,查找过程中我们保持LineLeft和RowRight指针不变,待搜索的行范围[RowLeft,RowRight],待搜索的列范围[LineLeft,LineRight]
  • 😃先对第RowLeft行进行二分查找,如上图所示,7不存在于第RowLeft行,则我们需要通过二分查找接口定位比target小最大元素(上图中的4):剑指offer练习日志01--数组小练习剑指offer练习日志01--数组小练习😃接下来更新LineRight指针(同时令RowLeft加一):剑指offer练习日志01--数组小练习
  • 😃这时候我们的查找范围就变成了下图中的矩阵:剑指offer练习日志01--数组小练习
  • 😍可见查找范围一下子缩小了一大半😍
  • 😍接下来再对第LineRight列进行二分查找,则可以找到元素7
  • 😍在一般情况下,第LineRight列进行二分查找若没有找到target,我们同样需要通过二分查找接口定位比target小最大元素并且更新RowLeft指针,接着重复上述行列交叉二分查找的过程直到找到target或RowLeft(或LineRight)指针超出边界条件为止
  • 😍上述算法的时间复杂度在大多数情况下可以达到log(Row*Col)(相当于每次单趟查找都可以二分整个矩阵) 

算法实现:

  • 😭算法的边界问题很伤人脑筋😭
class Solution
{
	//行二分查找接口
    //参数Line标识待查找的行标
	bool binaryLineSearch(vector<vector<int>>& arr, int Line, int* returnlimit,
		                  int left, int right, int target)
	{

		while (right >= left)
		{
			int mid = left + ((right - left) >> 2);
			if (arr[Line][mid] > target)		    //右边界缩进
			{
				right = mid - 1;
			}
			else if (arr[Line][mid] < target)       //左边界缩进
			{
				left = mid + 1;
			}
			else
			{
				*returnlimit = mid;
				return true;
			}
		}
		*returnlimit = right;						//返回行上比target小的最大元素列下标
		return false;
	}

	//列二分查找接口
    //参数Row标识待查找的列标
	bool binaryRowSearch(vector<vector<int>>& arr, int Row, int* returnlimit,
		                 int left, int right, int target)
	{
		if (Row < 0)
		{
			return false;
		}
		while (right >= left)
		{
			int mid = left + ((right - left) >> 2);
			if (arr[mid][Row] > target)				   //右边界缩进
			{
				right = mid - 1;
			}
			else if (arr[mid][Row] < target)           //左边界缩进
			{
				left = mid + 1;
			}
			else
			{
				*returnlimit = mid;
				return true;
			}
		}
		*returnlimit = right;                         //返回列上比target小的最大元素行下标
		return false;
	}


public:
	bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
	{
		int height = matrix.size();
		if (height == 0)
		{
			return false;
		}
		int lenth = matrix[0].size();



		//列查找右边界不动
		const int  Rowright = height - 1;
		int RowLeft = 0;
		int Row = 0;     //用于记录下一次要进行二分查找的行


		//行查找左边界不动
		const int LineLeft = 0;
		int  LineRight = lenth - 1;
		int Line = 0;    //用于记录下一次要进行二分查找的列



		//当矩阵只有一行(或一列)元素时,则只需进行一次行(或列)的二分查找
		if (LineRight == 0)
		{
			return binaryRowSearch(matrix, 0, &Line, 0, Rowright, target);
		}
		else if (Rowright == 0)
		{
			return binaryLineSearch(matrix, 0, &Row, 0, LineRight, target);
		}



		//行列交叉二分查找
		while (LineRight >= 0 && LineRight <= lenth - 1 && RowLeft >= 0 && 
               RowLeft <= height - 1)
		{
			if (binaryLineSearch(matrix, Line, &Row, LineLeft, LineRight, target))
			{
				return true;      //找到元素返回true
			}
			LineRight = Row;
			++RowLeft;
			if (binaryRowSearch(matrix, Row, &Line, RowLeft, Rowright, target))
			{
				return true;     //找到元素返回true
			}
			++Line;
			RowLeft = Line;
		}
		return false;
	}
};

剑指offer练习日志01--数组小练习

 剑指offer练习日志01--数组小练习文章来源地址https://www.toymoban.com/news/detail-423417.html

到了这里,关于剑指offer练习日志01--数组小练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【剑指offer】数组中重复的数字

    👑专栏内容:力扣刷题 ⛪个人主页:子夜的星的主页 💕座右铭:前路未远,步履不停 剑指offer:数组中重复的数字 在一个长度为 n 的数组里的所有数字都在 0 0 0 到 n − 1 n-1 n − 1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复,也不知道每个数字重复了几

    2024年01月20日
    浏览(51)
  • 【剑指 offer】旋转数组的最小数字

    ✨个人主页:bit me👇 ✨当前专栏:算法训练营👇 核心考点:数组理解,二分查找,临界条件 描述: 有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这

    2023年04月20日
    浏览(52)
  • 剑指 Offer 66. 构建乘积数组(中等)

    题目: 作者:Krahets 链接:https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solutions/208840/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/ 来源:力扣(LeetCode)

    2024年02月10日
    浏览(33)
  • 【剑指offer|图解|数组】寻找文件副本 + 螺旋遍历二维数组

    🌈个人主页: 聆风吟 🔥系列专栏: 数据结构、剑指offer每日一练 🔖少年有梦不应止于心动,更要付诸行动。 ⌈ 在线OJ链接,可以转至此处自行练习 ⌋ 设备中存有 n 个文件,文件 id 记于数组 documents 。若文件 id 相同,则定义为该文件存在副本。请返回任一存在副本的文件

    2024年02月05日
    浏览(39)
  • 【剑指offer|1.数组中重复的数字】

    : 长度为n的数组nums中所有数字都在0~n-1范围内 返回任意一个重复的数字 总体时间复杂度和空间复杂度分析: 修改数组的方法: 因为有n个元素,每一个元素都在0~(n-1)范围内,如果元素不重复的话, 对数组重排之后,下标和元素值之间应该是一一对应的关系 但是因为

    2023年04月22日
    浏览(39)
  • 剑指 Offer 03. 数组中重复的数字

    剑指 Offer 03. 数组中重复的数字 利用题目的限制条件: 所有数字都在 0~n-1 的范围内 通过交互让数字和下标一一对应,如果有多个数字对应同一个下标,那就找到了答案。 另一种写法

    2024年02月11日
    浏览(37)
  • 剑指offer03.数组中重复的数字

    看到这道题的第一眼想到的是先给它排序,然后双指针从左往右遍历,写了一个冒泡排序,但是我想到了应该会超时,因为冒泡时间复杂度是n的平方,输入大小时10000,肯定会超时,然后右又看了一下题目看到数字都是0-n-1,灵感一下子就来了,我先创建一个等大的自然数数

    2024年02月11日
    浏览(40)
  • 剑指offer -- 二维数组中的查找

    二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 暴力查找法: 是一种简单直接的解决方法,可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素,逐个与目标值进行比较。 具体步骤如下: 从数组的第一行第一列开始,逐行逐列地遍历数组的每个元素。 对

    2024年02月06日
    浏览(91)
  • 剑指offer45 把数组排成最小的数

    链接 其实这道题,大概看完就知道是一个排序的问题,无非就是数组中的元素以一个合适的位置排好序,这样从头加到尾,组成的整体数字最小!(题目中也暗示你排序问题了) 个人捉摸了一会,这道题能很好地锻炼仿函数的编写规则和库函数sort()的配套使用,还有就是巧妙地

    2024年01月16日
    浏览(43)
  • 剑指 Offer 51. 数组中的逆序对

    剑指 Offer 51. 数组中的逆序对   【归并】朴实无华的一个归并排序的应用,对于一个数组,我们通过归并排序来从大到小进行排序,在合并的过程中如果前面区间有比后面区间大的元素,那么后面区间从这个元素开始一直到结束都能和前面区间的那个数组成逆序对。 举个🌰

    2024年02月02日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包