澳门新葡8455手机版-澳门新葡8455最新网站

您的位置:澳门新葡8455手机版 > 新闻资讯 > 用两个栈实现长度为k的队列的入队时间复杂度

用两个栈实现长度为k的队列的入队时间复杂度

2019-10-09 08:08

本连串导航:剑指offerjava完毕导航帖

本连串导航:剑指offerjava达成导航帖

面试题39:数组中冒出次数超过八分之四的数字

面试题59:滑动窗口的最大值

主题素材必要:搜索数组中冒出次数超越数主任度百分之五十的数字。如输入{1,2,3,2,2,2,5,4,2},则输出2。

难题须求:给定二个数组和滑动窗口的大大小小,请搜索全数滑动窗口的最大值。比方,输入数组{2,3,4,2,6,2,5,1}和数字3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}。

解题思路:因为该数字的产出次数超越了数老董度的二分之一,因而得以将标题转化为求数组的中位数。假使依据那个思路,有以下三种方法缓和:排序后求中位数、用快排的分区函数求中位数,那三种思路都相比较轻松,此处不再赘言。书中还关系一种思路,相当抢眼,可以看成一种特殊的缓存机制。该思路须要三个整型的value变量和一个整型的count变量,记录缓存值与该缓存值被打中的次数。缓存法则以及实施步骤如下:

解题思路:思路1:使用暴力求解。假如滑动窗口长度为k,每到三个点都向前遍历k-1个节点,那么总时间复杂度为o。

步骤1: 缓存值value,命中次数count均初始化为0。步骤2: 从头到尾依次读取数组中的元素,判断该元素是否等于缓存值: 步骤2.1:如果该元素等于缓存值,则命中次数加一。 步骤2.2:如果该元素不等于缓存值,判断命中次数是否大于1: 步骤2.2.1:如果命中次数大于1,将命中次数减去1。 步骤2.2.2:如果命中次数小于等于1,则令缓存值等于元素值,命中次数设为1步骤3: 最终的缓存值value即为数组中出现次数超过一半的数字。

思路2:长度为k的滑行窗口其实能够当作叁个系列,而滑行窗口的运动能够充当队列的出队和入队,因而本题能够转账为求长度为k的种类的最大值。借助以前做过的9.用四个栈实现队列和30.包蕴min函数的栈,大家得以兑现求队列的最大值。上边大家分析下时间与上空复杂度。用四个栈完成长度为k的队列的入队时间复杂度o,出队时间复杂度o,空间复杂度为o;富含最值函数的栈的光阴复杂度为o,空间复杂度为o。由此长度为k的队列的一回出队+入队操作时间复杂度为o,空间复杂度为o。而以此窗口供给达成在长度为n的数组上百折不回的滑动,因而,本解法的岁月复杂度为o,空间复杂度o。

此方法时间复杂度o,空间复杂度o,落成简单。

思路3:把也许形成最大值数字的下标放入双端队列deque,进而减少遍历次数。首先,全体在未曾翻动后边数字的状态下,任何三个节点都有望形成有些状态的滑行窗口的最大值,由此,数组中别的一个因素的下标都会入队。关键在于出队,以下二种情形下,该下标对应的数字不会是窗口的最大值须求出队:该下标已经在窗口之外,比如窗口长度为3,下标5入队,那么最大值只恐怕在下标3,4,5中冒出,队列中只要有下标2则须求出队;后三个因素大于前边的要素,那么前面包车型地铁要素出对,举个例子目前队列中有下标3、4,data[3] = 50,data[4]=40,下标5入队,但data[5] = 70,则队列中的3,4都亟需出队。数组{2,3,4,2,6,2,5,1}的尺寸为3的滑行窗口最大值求解步骤如下

package chapter5;/** * Created with IntelliJ IDEA. * Author: ryder * Date : 2017/7/28 * Time : 17:51 * Description: 数组中出现次数超过一半的数字 **/public class P205_MoreThanHalfNumber { //转化为topK问题,使用快排的分区函数解决,求第targetIndex+1小的数字(下标为targetIndex) //书中说这种方法的时间复杂度为o,但没懂为什么。网上也有人说为o public static int moreThanHalfNum1(int[] data){ if(data==null || data.length==0) return 0; int left = 0,right=data.length-1; //获取执行分区后下标为k的数据值(即第k+1小的数字) int k = data.length>>>1; int index = partition(data,left,right); while{ if(index>k) index = partition(data,left,index-1); else index = partition(data,index+1,right); } return data[k]; } //分区,[小,povot,大] public static int partition(int[] data,int left,int right){ int pivot = data[left]; while(left<right){ while (left<right && data[right]>=pivot) right--; if(left<right) data[left] = data[right]; while (left<right && data[left]<pivot) left++; if(left<right) data[right] = data[left]; } data[left] = pivot; return left; } //根据数组特点进行记录、查找,时间复杂度o public static int moreThanHalfNum2(int[] data){ if(data==null || data.length==0) return 0; int count = 1; int value = data[0]; for(int i=1;i<data.length;i++){ if(data[i]==value) count++; else if(data[i]!=value && count==1) value = data[i]; else count--; } return value; } public static void main(String[] args){ int[] data = {1,2,3,2,2,2,5,4,2}; System.out.println(moreThanHalfNum2; System.out.println(moreThanHalfNum1; }}
步骤 插入数字 滑动窗口 队列中的下标 最大值1 2 2 0 N/A 2 3 2,3 1 N/A 3 4 2,3,4 2 4 4 2 3,4,2 2 4 5 6 4,2,6 4 6 6 2 2,6,2 4 6 7 5 6,2,5 4 6 8 1 2,5,1 6 5 

运维结果

时光复杂度在o之间,空间复杂度o。思路3的代码实现如下:

22
package chapter6;import java.util.ArrayDeque;import java.util.Deque;/** * Created with IntelliJ IDEA * Author: ryder * Date : 2017/8/18 * Time : 17:58 * Description:滑动窗口的最大值 **/public class P288_MaxInSlidingWindow { //把可能会成为最大值的下标存储下来,从而降低扫描次数 public static int[] maxInWindows(int[] data,final int size){ if(data==null ||data.length==0||data.length<size) return new int[0]; int[] result = new int[data.length-size+1]; Deque<Integer> deque = new ArrayDeque<>(); for(int i=0;i<size-1;i++){ while (!deque.isEmpty()&&data[i]>=data[deque.getLast deque.removeLast(); deque.addLast; } for(int i=size-1;i<data.length;i++){ while (!deque.isEmpty()&&i-deque.getFirst()+1>size) deque.removeFirst(); while (!deque.isEmpty()&&data[deque.getLast()]<=data[i]) deque.removeLast(); deque.addLast; result[i-] = data[deque.getFirst()]; } return result; } public static void main(String[] args){ int[] data = new int[]{2,3,4,2,6,2,5,1}; int[] result = maxInWindows; for(int i=0;i<result.length;i++){ System.out.print(result[i]); System.out.print; } }}

运营结果

4 4 6 6 6 5

本文由澳门新葡8455手机版发布于新闻资讯,转载请注明出处:用两个栈实现长度为k的队列的入队时间复杂度

关键词: