算法练习day7——190325（比较器、不基于比较的排序、maxGap、数组实现栈和队列、minStack）
生活随笔
收集整理的這篇文章主要介紹了
算法练习day7——190325（比较器、不基于比较的排序、maxGap、数组实现栈和队列、minStack）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1.比較器
1.1 Arrays.sort()
Arrays.sort(數組)
- 若其中的數組元素時自定義類型，報錯；
- 若為基本類型，則按值排序。
Arrays.sort(數組，自己定義的比較器)：
- 會按定義的比較器進行比較排序。
1.2 比較器
是一個自己定義的類。
類名 implements Comparator<Student>
實現其中的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<arr.length; i++)System.out.println(arr[i].id+"--"+arr[i].name+"--"+arr[i].age);System.out.println("**************************");} }class IdAscendingComparator implements Comparator<Student>{@Overridepublic int compare(Student arg0, Student arg1) {/** if(arg0<arg1)* return 負數；* else if(arg0>arg1)* return 正數；* else* return 0;*/return arg0.id-arg1.id;} }class IdDscendingComparator implements Comparator<Student>{@Overridepublic int compare(Student arg0, Student arg1) {return arg1.id-arg0.id;} }class AgeAscendingComparator implements Comparator<Student>{@Overridepublic int compare(Student arg0, Student arg1) {return arg0.age-arg1.age;} }class AgeDscendingComparator implements Comparator<Student>{@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<Student> 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
紅黑樹結構。
系統提供的一個有序的結構，都會伴隨著一個比較器的構造。這個比較器告訴這個結構怎么組織。
——基于比較的排序是重點。
2.不基于比較的排序
時間復雜度：
- 遍歷數組的時間
額外空間復雜度：
都是穩定的。
與被排序的樣本的實際數據狀況很有關系， 所以實際中并不經常使用。
計數排序就是桶排序的一個具體體現。
3.給定一個數組， 求如果排序之后， 相鄰兩數的最大差值， 要求時間復雜度O(N)， 且要求不能用非基于比較的排序。
3.1 舉例：
原始數據：
排序之后：
所以應該返回3.
3.2 實現方式
借用了桶的概念，但是未用桶排序。
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;i<n;i++) {max=max>arr[i]?max:arr[i];min=min<arr[i]?min:arr[i];}System.out.println("min:"+min+" max:"+max);int[] mins=new int[n+1];int[] maxs=new int[n+1];boolean[] flag=new boolean[n+1];if(min==max)return result;//設置桶0和桶nmins[0]=min;maxs[0]=min;mins[n]=max;maxs[n]=max;for(int i=0;i<n;i++) {int index=(int)((arr[i]-min)*n/(max-min));System.out.println("index:"+index);if(flag[index]==false) {mins[index]=arr[i];maxs[index]=arr[i];flag[index]=true;}else {mins[index]=Math.min(mins[index], arr[i]);maxs[index]=Math.max(maxs[index], arr[i]);}}int lastmax=maxs[0];for(int i=1;i<n;i++) {if(flag[i]==true) {result=mins[i]-lastmax;lastmax=maxs[i];}}return result;} }運行結果：
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.用數組結構實現大小固定的棧和隊列
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<array.length，則將這個數放在array[last]的位置，同時last++；否則報錯；
如果一個數要出隊列，若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} }運行結果：
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<Integer> data;Stack<Integer> min;public MyStack() {this.data=new Stack<Integer>();this.min=new Stack<Integer>();}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棧彈出棧頂元素。
總結
以上是生活随笔為你收集整理的算法练习day7——190325（比较器、不基于比较的排序、maxGap、数组实现栈和队列、minStack）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 算法练习day6——190323（求中位
- 下一篇： 算法练习day8——190326（猫狗队