算法练习day7——190325（比较器、不基于比较的排序、maxgap、数组实现栈和队列、minstack） -ag凯发k8国际

1.1 arrays.sort()

arrays.sort(数组)

• 若其中的数组元素时自定义类型，报错；
• 若为基本类型，则按值排序。

arrays.sort(数组，自己定义的比较器)：

• 会按定义的比较器进行比较排序。

1.2 比较器

是一个自己定义的类。

类名 implements comparator

实现其中的public int compare(student o1,student o2)方法：

• 此方法返回一个负数：说明o1更小，即o1应该排在前面；
• 返回一个正数：第二个应该放在前面；
• 返回0：两个一样大

c 中重载运算符就是自己定义比较器的一种方式。

package comparator;import java.util.arrays; import java.util.comparator;class student{int id;string name;int age;public student(int id,string name,int age) {this.id=id;this.name=name;this.age=age;} } public class comparatortest {public static void main(string[] args) {student[] students=new student[3];students[0]=new student(3,"llll",23);students[1]=new student(2,"ssss",18);students[2]=new student(1,"qqqq",34);//arrays.sort(students);//printarray(students);arrays.sort(students,new idascendingcomparator());printarray(students);arrays.sort(students,new iddscendingcomparator());printarray(students);arrays.sort(students,new ageascendingcomparator());printarray(students);arrays.sort(students,new agedscendingcomparator());printarray(students);}public static void printarray(student[] arr) {for(int i=0;i{@overridepublic int compare(student arg0, student arg1) {/** if(arg0arg1)* return 正数；* else* return 0;*/return arg0.id-arg1.id;} }class iddscendingcomparator implements comparator{@overridepublic int compare(student arg0, student arg1) {return arg1.id-arg0.id;} }class ageascendingcomparator implements comparator{@overridepublic int compare(student arg0, student arg1) {return arg0.age-arg1.age;} }class agedscendingcomparator implements comparator{@overridepublic int compare(student arg0, student arg1) {return arg1.age-arg0.age;} }

运行结果：

1.3 priorityqueue

堆结构也可用比较器

优先级队列就是堆。

若没有给比较器，则报错。

package comparator;import java.util.priorityqueue;public class priorityqueuetest {public static void main(string[] args) {student student1=new student(3,"llll",23);student student2=new student(2,"ssss",18);student student3=new student(1,"qqqq",34);priorityqueue heap=new priorityqueue<>(new agedscendingcomparator());//按age大的放在头部heap.add(student1);heap.add(student2);heap.add(student3);while(!heap.isempty()) {student stu=heap.poll();//弹出堆顶元素，堆大小-1；system.out.println(stu.id "--" stu.name "--" stu.age);}} }

运行结果：

1.4 treemap

红黑树结构。

系统提供的一个有序的结构，都会伴随着一个比较器的构造。这个比较器告诉这个结构怎么组织。

——基于比较的排序是重点。

时间复杂度：

• 遍历数组的时间

额外空间复杂度：

都是稳定的。

与被排序的样本的实际数据状况很有关系， 所以实际中并不经常使用。

计数排序就是桶排序的一个具体体现。

3.1 举例：

原始数据：

排序之后：

所以应该返回3.

3.2 实现方式

借用了桶的概念，但是未用桶排序。

n个数据，准备n 1个桶；用一个全局变量记录最大差值。

遍历数组，找到min和max

若min=max，整个数组只有一种数，返回0；

若不等，min放入桶0，max放入桶n

将min~max均分成n份，对应n 1个桶，如下图：

其他数属于哪个范围，放入对应的桶。

每个桶设置三个属性：

min

max

flag(boolean)：表示这个桶是否有元素进入过

若x进入桶m时，flag=false，则令flag=true，min=max=x;

若y进入桶m时，flag=true，则只更新min和max

遍历完后，找每个桶的flag

若为false，直接跳下一个；

若为true，找到此桶的前一个非空桶，此桶的min-前非空桶的max得到这两个桶的差值。

更新最大差值。

3.3 最大差值肯定跨桶的原因分析

如上图，排序后，相临的两个数可能来自同一个桶（11，15），也可能来自不同的桶（15，21）。

n个数，n 1个桶，根据鸽舍原理，肯定存在一个空桶。

存在空桶，就可以说明：最大差值一定不来自相同的桶。

因为：

空桶左肯定存在离它最近的非空桶，空桶右边也肯定存在离它最近的布控的桶（最起码桶0和桶n都非空）。

左.max-右.min>桶表示的范围；

一个桶内部的两个元素的差值<桶表示的范围

所以最大差值不会是同一桶中的两个元素——只用关心不同桶的元素。

为什么不直接找非空桶，得到最大差值=左.max-右.min？

如上图，最大差值为19，是相邻两桶产生的差值。

有空桶，只是说明最大差值肯定不是在同一桶中，但不是说最大差值一定来自空桶两侧非空桶的差值。

3.4 代码实现

package solution;public class maxgap {public static void main(string[] args) {int[] array= {3,1,6,2,7};system.out.println("maxgap=" maxgap(array));}public static int maxgap(int[] arr) { int result=0;if (arr == null || arr.length < 2) {return result;}int min=integer.max_value;int max=integer.min_value;int n=arr.length;for(int i=0;iarr[i]?max:arr[i];min=min运行结果：

3.4.1 结果分析

元素，其中最大值为7，最小值为1。

5个元素，需要6个桶。

首先，将max-min=7-1=6进行5等分，6/5=1.2，得每段距离长1.2。

然后进行每个元素属于的桶号的计算：

• 3：(3-1)/1.2=2/1.2=1（取整）；
• 6：(6-1)/1.2=5/1.2=4；
• 2：(2-1)/1.2=1/1.2=0；

所以分桶结果如下图：

所以result=3;

3.4.2 对于计算桶号的公式的分析

即就是：

先算出每段距离的长度（），再求出当前元素据起点min的距离（），最后用后者除以前者就得到当前元素所属于的桶号（index）。

4.1 实现栈

4.1.1 分析

index：表示新进来的数应该放置的位置。

一个数入栈时，若index 1>size，则报错；否则这个数放在array[index]的位置，然后index ；

一个数出栈时，若index-1<0，则报错；否则弹出放在array[index-1]位置上的数，然后index--。

4.1.2 代码实现

package solution;class arraystack{integer[] array;integer size; public arraystack(int initsize) {if(initsize<0)throw new illegalargumentexception("the init size is less than 0");elsearray=new integer[initsize];size=0;}public void push(int num) {if(size==array.length)throw new arrayindexoutofboundsexception("the queue is full");elsearray[size ]=num;}public integer peek() {if(size==0)throw new arrayindexoutofboundsexception("the queue is empty");elsereturn array[size-1];}public integer pop() {if(size==0)throw new arrayindexoutofboundsexception("the queue is empty");elsereturn array[--size];} } public class arraytostack {public static void main(string[] args) {arraystack as=new arraystack(3);as.push(3);system.out.println("peek:" as.peek());as.push(24);system.out.println("pop:" as.pop());system.out.println("pop:" as.pop());//system.out.println("pop:" as.pop());} }

运行结果：

若为注释掉最后一句pop，运行结果为：

4.2 实现队列

4.2.1 分析

如果一个数要入队列，若size

如果一个数要出队列，若size>0，则array[first]位置上的数出队列，同时first ；否则报错。

注：当last和first到达最后一个元素时，让它们下一个位置为0位置。

（last和first之间无关系）

4.2.2 代码实现

package solution;class arrayqueue{integer[] array;integer first;//出队列时的下标integer last;//入队列时的下标integer size;public arrayqueue(int initsize) {if(initsize<0)throw new illegalargumentexception("the init size is less than 0");elsearray=new integer[initsize];size=0;last=0;first=0;}public void push(int num) {if(size==array.length)throw new arrayindexoutofboundsexception("the queue is full");else {array[last]=num;last=last==array.length-1?0:last 1;size ;}}public integer peek() {if(size==0)throw new arrayindexoutofboundsexception("the queue is empty");else return array[first];}public integer poll() {if(size==0)throw new arrayindexoutofboundsexception("the queue is empty");else {size--;first=first==array.length-1?0:first 1;return array[first];}} } public class arraytoqueue {public static void main(string[] args) {arrayqueue as=new arrayqueue(3);as.push(7);system.out.println("peek:" as.peek());as.push(6);system.out.println("pop:" as.poll());//7出as.push(5);as.push(9);//as.push(4);system.out.println("pop:" as.poll());//6system.out.println("pop:" as.poll());//5} }

运行结果：

【要求】
1． pop、 push、 getmin操作的时间复杂度都是o(1)。
2． 设计的栈类型可以使用现成的栈结构。

5.1 方法一

5.1.1 分析：

准备两个栈：data、min

入栈：

第一个元素，压入data、min栈；

后面剩余元素，依次压入data栈；若当前入栈元素比min栈栈顶元素小，则入min栈，否则再一次压入min栈栈顶元素。

出栈：

两个栈同时弹出元素。

5.1.2 代码实现

package solution;import java.util.stack;class mystack{stack data;stack min;public mystack() {this.data=new stack();this.min=new stack();}public void push(int num) {if(data.isempty()) {data.push(num);min.push(num);}if(num<=min.peek()) {data.push(num);min.push(num);}else {data.push(num);min.push(min.peek());}}public integer pop() {if(data.isempty())throw new runtimeexception("your stack is empty.");min.pop();return data.pop();}public integer getmin() {if(data.isempty())throw new runtimeexception("your stack is empty.");return min.peek();} } public class stackgetmin {public static void main(string[] args) {mystack ms=new mystack();ms.push(4);ms.push(5);ms.push(3);ms.push(6);system.out.println("min:" ms.getmin());system.out.println(ms.pop());system.out.println(ms.pop());system.out.println("min:" ms.getmin());} }

运行结果：

5.2 方法二

5.2.1 分析：

准备两个栈：data、min

入栈：

第一个元素，压入data、min栈；

后面剩余元素，依次压入data栈；若当前入栈元素比min栈栈顶元素小，则入min栈，否则不如min栈。

出栈：

若当前弹出的data栈顶元素=min栈栈顶元素，两个栈都弹出栈顶元素，否则只有data栈弹出栈顶元素。

总结

以上是ag凯发k8国际为你收集整理的算法练习day7——190325（比较器、不基于比较的排序、maxgap、数组实现栈和队列、minstack）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。