“Rotate sorted array”系列问题

2024-05-16 02:08

本文主要是介绍“Rotate sorted array”系列问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定一个排序的数组,进行数组旋转之后引出了一系列的问题,这里将遇到的相关问题做一个总结,并给出解决方法,备用所需。

有序数组旋转操作

这个问题是所有系列问题的起始,给一个有序数组,使用这个操作进行旋转,得到的数组就可以以之为其他问题的基础进行引申。

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

这个问题的解决思路有如下几个:
1. 单独申请一个数组,将下标间隔之后进行拷贝
2. 将前n-k个元素添加到后面,然后将前面的n-k个元素删除(利用vector的push_backerase
3. 进行原地操作,常数级的空间

上述思路的第三个比较巧妙,使用常数级的原地操作。代码如下:

void rotate(int* nums, int numsSize, int k) {int prev = numsSize > 0 ? nums[0] : 0, next = prev;int i = 0, j = 0;for(int n = 0; n < numsSize; ++n){i = (i + k) % numsSize;prev = next;next = nums[i];nums[i] = prev;if (i == j) //关键所在,如果出现重复,需要进行偏移操作{next = nums[++j];i++;}}
}

寻找最小值(无重复元素)

对于旋转过的有序数组,如果没有重复元素,那么依然可以利用有序性质来进行二分查找,来寻找元素,首先是寻找最小值。
这里假定数组的顺序是升序的,利用的原理依然是通过中间元素与首尾元素之间的关系。如果中间元素大于首元素,则从首元素到中间元素间(包含边界)都是有序的,无序部分在后一半区间,此时如果尾元素小于中间元素,则最小值在后半区间,否则在前半区间;如果中间元素小于首元素,则一定是尾部的较大元素被旋转到了头部,后半区间是有序的,最小值肯定在包括中间元素的前半区间。
上述思路的递归版本代码实现如下,时间复杂度是O(logN)

    int findMin(vector<int>& nums) {return findMinHelper(nums, 0, nums.size() - 1);}int findMinHelper(vector<int> & a, int s, int e){if (s == e) return a[s];int m = (s + e) / 2;if (a[m] > a[s]){if (a[e] < a[m]) return findMinHelper(a, m + 1, e);else return findMinHelper(a, s, m);}else{return findMinHelper(a, s, m);}}

寻找最小值(有重复元素)

当存在重复元素时,需要考虑中间元素与首元素相等的情况:此时需要考虑两边,进行查找之后比较大小。其他情况类似。此时最差情况可能出现全部元素都相同,最差情况的复杂度为O(N)

    ///递归版本int findMin(vector<int>& nums) {return findMinHelper(nums, 0, nums.size() - 1);}int findMinHelper(vector<int> & a, int s, int e){if (s == e) return a[s];int m = (s + e) / 2;if (a[m] == a[s]){int l = findMinHelper(a, s, m);int r = findMinHelper(a, m, e);return l > r ? r : l;}else if(a[m] > a[s]){if (a[e] < a[m]) return findMinHelper(a, m + 1, e);else return findMinHelper(a, s, m);}else{return findMinHelper(a, s, m);}}///非递归版本int findMin(vector<int> & nums){int l = 0, r = nums.size() - 1;while(l < r){int m = l + (r - l) / 2;if (nums[m] == nums[l]){if (nums[r] >= nums[m]) --r;else ++l;}else if (nums[m] > nums[l]){if (nums[r] < nums[m]) l = m + 1;else r = m;}else r = m;}return nums[l];}

查找指定元素(无重复元素)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.

当没有重复元素时,套用前面的查找最小元素的思路即可:

int search(vector<int> & nums, int target)
{int l = 0, r = nums.size() - 1;while(l < r){int m = l + (r - l) / 2;if (nums[m] == target) return m;if (nums[m] > nums[l]){//target在前半区间,target可能等于首元素,故大于等于号不可少if (target < nums[m] && target >= nums[l]) r = m - 1;else l = m + 1;}else{//target在后半区间,target可能等于尾元素,大于等于号不可少if (target > nums[m] && target <= nums[r]) l = m + 1;else r = m - 1;}}if (l == r && nums[l] == target) return l;return -1;
}

查找指定元素(有重复元素)

套用前面的有重复元素查找最小元素的思路,针对相等的情况进行区别对待即可。下面为非递归版本,递归版本与前面类似。

    int search(vector<int> & nums, int target){int l = 0, r = nums.size() - 1;while(l < r){int m = l + (r - l) / 2;if (nums[m] == target) return m;if (nums[m] == nums[l]){if (nums[r] >= nums[m]) --r;else ++l;}else if (nums[m] > nums[l]){if (target >= nums[l] && target < nums[m]) r = m - 1;else l = m + 1;}else{if ( target > nums[m] && target <= nums[r]) l = m + 1;else r = m - 1;}}return nums[l];}

这篇关于“Rotate sorted array”系列问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0