网站建设资讯站,常州网站建设培训,制作一个app需要什么技术,html5搭建网页游戏 个人主页#xff1a;秋风起#xff0c;再归来~ 文章所属专栏#xff1a;《剑指offer》典型编程题的极练之路 … 个人主页秋风起再归来~ 文章所属专栏《剑指offer》典型编程题的极练之路 个人格言悟已往之不谏知来者犹可追 克心守己律己则安 目录
编辑 一、面试题1数组中重复的数字查重
1.1 题目一找出数组中重复的数字
1.2 题目二不修改数组找出重复的数字 二、面试题2二维数组中的查找 三. 完结散花 一、面试题1数组中重复的数字查重
1.1 题目一找出数组中重复的数字 题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如如果输入长度为7的数组[2,3,1,0,2,5,3]那么对应的输出是2或者3。存在不合法的输入的话输出-1 数据范围0≤n≤10000 进阶时间复杂度 O(n) 空间复杂度O(n) 示例 输入
[2,3,1,0,2,5,3]
返回值
2
说明
2或3都是对的 牛客网上该题目链接点击进入 1.1.1排序法
解决这个问题我们首先可以想到一个非常简单的方法就是把数组进行排序从有序的数组中找出重复的元素是一件很容易的事情只需要从头到尾扫描排序后的数组就可以了。排序一个长度为n的数组需要O(nlongn)的时间
1.1.2 哈希表
我们还可以用哈希表来解决这个问题。从头到尾按顺序扫描数组的每个数字每扫描到一个位置的时候都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字就把他加入哈希表。如果哈希表里已经存在该数字就找到一个重复的数字。这个算法的时间复杂度是O(n)但它提高效率是以一个大小为O(n)的哈希表为代价的。
1.1.3 下标索引
我们注意到数组中的数字都在0~n-1的范围内。如果数组中没有重复的数字那么排序后数字i将出现在下标为i的位置。由于数组中有重复的数字有些位置可能存在多个数字同时有些位置可能没有位置。
现在我们重新排列一下这个数组。从头到尾依次扫描数组中的每一个数组当扫描到下标为i的数字m时如果这个数字等于i(mi)则我们接着扫描下一个数字如果不是那我们就把它m和下标为m的那个元素先进行比较如果m与下标为m的元素的大小相等那这个数m就是重复的数字如果不相等那我们就将这两个数字进行交换即把m放到下标为m的位置。接下来我们就重复这个比较交换的动作直到我们发现一个重复的数字。
画个图理解一下 牛客网上解题的代码如下~
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param numbers int整型一维数组 * param numbersLen int numbers数组长度* return int整型*/
int duplicate(int* numbers, int numbersLen ) {// write code hereif(numbersNULL||numbersLen0)return -1;//第一层循环遍历数组元素for(int i0;inumbersLen;i){//第二层循环将该元素放到和其值相等的下标的位置while(numbers[i]!i){if(numbers[i]numbers[numbers[i]]){return numbers[i];}int tmp numbers[i];numbers[i]numbers[tmp];numbers[tmp]tmp;}}return -1;
}
代码中尽管有两重循环但每个数字最多只要交换两次就能找到属于他自己的完位置因此总的时间复杂度为O(n)。另外所有的操作都是在原数组上完成的不需要分配额外的内存空间所以空间复杂度为O(1)。 1.2 题目二不修改数组找出重复的数字 题目描述 在一个长度为n1的数组里的所有数字都在1~n的范围内所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字但不能修改输入的数组。 例如如果输入长度为8 的数组{2,3,5,4,3,2,6,7}那么对应输出的是重复的数字是2或3。 1.2.1 创建临时数组
不能修改临时数组那我们就创建一个临时的大小为n1的数组将原数组中数字为m的元素复制放到临时数组下标为m的位置上在放入之前我们比较一下它们的值是否相等就可以很容易的找到重复的数字了。不过我们创建了一个大小为n1的数组所以这种算法的空间复杂度为O(n)时间复杂度也是O(n)。
那我们接下来就尝试避免使用O(n)的空间看能不能解题~
1.2.2 二分查找
我们假设数组中没有重复的数字那么对于1~n范围内的数字我们在遍历原数组后这些数字出现的次数一定为n但如果原数组中有重复的数字并且在1~n内存在原数组中重复的数字我们在遍历原数组后这些数字出现的次数一定大于n。
所以基于以上的分析我们不妨借鉴二分查找法的思路将将我们要查重的数据一分为二来查找。
下面举一个栗子进行分析啦~ 代码实现如下~
int countrange(int*numbers,int numbersLen,int start,int middle){int count0;for(int i0;inumbersLen;i){if(numbers[i]startnumbers[i]middle){count;}}return count;}
int duplicate(int* numbers, int numbersLen ) {// write code hereif(numbersNULL||numbersLen0)return -1;int start0;int endnumbersLen-1;while(startend){int middle((end-start)1)start;//计算局部范围内数字出现的次数int countcountrange(numbers,numbersLen,start,middle);if(startend)//找到最后一个数{if(count1)return start;elsebreak;}if(count(middle-start1))//前半段有重{endmiddle;}else //后半段有重{startmiddle1;}}return -1;
}
需要指出的是上述代码按照二分查找的思路如果输入长度为n的数组那么函数countrange将被调用O(logn)次每次需要O(n)的时间因此总的时间复杂度为O(nlogn)空间复杂度为O(1)。和前面提到的需要O(n)的辅助空间的算法相比这种算法相当于以时间换空间 二、面试题2二维数组中的查找 题目描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 力扣上的题目链接点击进入 在具有上述特性的矩阵中搜索目标值的问题可以使用一种高效的算法来解决这种算法的时间复杂度为O(m n)。这个算法的基本思想是从矩阵的右上角或左下角开始搜索然后利用矩阵的特性来决定下一步的搜索方向。
以下是基于右上角开始搜索的算法步骤
初始化一个指针指向矩阵的右上角元素即第一行最后一列的元素。比较当前指针指向的元素与目标值的大小 如果当前元素等于目标值则搜索成功返回该元素的位置。如果当前元素大于目标值由于矩阵的每一列都是升序排列的因此目标值不可能在当前列的更下方位置所以将指针向左移动一列。如果当前元素小于目标值由于矩阵的每一行都是升序排列的因此目标值不可能在当前行的更左侧位置所以将指针向下移动一行。重复步骤2直到找到目标值或者指针移出矩阵的范围即指针指向的行列号超出矩阵的边界。如果指针移出矩阵范围仍未找到目标值则搜索失败返回相应的结果。 解题的具体代码如下~
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){if(matrixNULL||matrixSize0)return false;int row0;//从第0行int col(*matrixColSize-1);//从最后一列while(rowmatrixSizecol0){if(matrix[row][col]target)return true;else if(matrix[row][col]target)row;elsecol--;}return false;
} 三. 完结散花
好了这期的分享到这里就结束了~
如果这篇博客对你有帮助的话可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话可以点点关注避免找不到我了呢~
我们下期不见不散~~
