數(shù)據(jù)結(jié)構(gòu)與算法之字符憑拼接最低字典序和數(shù)據(jù)流中取中位數(shù)

---

目錄

字符憑拼接最低字典序

數(shù)據(jù)流中取中位數(shù)

---

1. 字符憑拼接最低字典序

題目描述

思路：

創(chuàng)建一個(gè)比較器，比較的內(nèi)容是(o1+o2).compareTo(o2+o1)·，返回的就是兩者之和中字典順序低的那一個(gè)。

在排序時(shí)應(yīng)用比較器，將字符數(shù)組進(jìn)行排序，然后依次組合即可。

代碼實(shí)現(xiàn)

import java.util.Arrays; import java.util.Comparator;public class Code_05_LowestLexicography {public static class MyComparator implements Comparator<String> {@Overridepublic int compare(String a, String b) {return (a + b).compareTo(b + a);}}public static String lowestString(String[] strs) {if (strs == null || strs.length == 0) {return "";}Arrays.sort(strs, new MyComparator());String res = "";for (int i = 0; i < strs.length; i++) {res += strs[i];}return res;}public static void main(String[] args) {String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };System.out.println(lowestString(strs1));String[] strs2 = { "ba", "b" };System.out.println(lowestString(strs2));}}

---

2. 數(shù)據(jù)流中取中位數(shù)

題目描述

思路

創(chuàng)建一個(gè)大根堆和小根堆，中位數(shù)就是兩者堆頂元素中的一個(gè)，返回即可

具體思路見代碼

代碼實(shí)現(xiàn)

import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue;public class Code_04_MadianQuick {public static class MedianHolder {private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());//調(diào)整大根堆和小根堆，兩者之元素差=2時(shí)，彈出堆頂元素添加到另一個(gè)堆private void modifyTwoHeapsSize() {if (this.maxHeap.size() == this.minHeap.size() + 2) {this.minHeap.add(this.maxHeap.poll());}if (this.minHeap.size() == this.maxHeap.size() + 2) {this.maxHeap.add(this.minHeap.poll());}}//添加元素/*** 1. 如果大根堆為null，直接加到大根堆* 2. 如果大根堆堆頂元素大于添加元素，則添加到大根堆，否則進(jìn)行else判斷* 3. 如果小根堆為null，直接添加到小根堆* 4. 如果小根堆堆頂元素大于添加元素，添加元素添加到大根堆，否則加入小根堆* 5. 最后要調(diào)整大根堆和小根堆的狀態(tài)*/public void addNumber(int num) {if (this.maxHeap.isEmpty()) {this.maxHeap.add(num);return;}if (this.maxHeap.peek() >= num) {this.maxHeap.add(num);} else {if (this.minHeap.isEmpty()) {this.minHeap.add(num);return;}if (this.minHeap.peek() > num) {this.maxHeap.add(num);} else {this.minHeap.add(num);}}modifyTwoHeapsSize();}//返回大根堆和小根堆之間的中位數(shù)public Integer getMedian() {int maxHeapSize = this.maxHeap.size();int minHeapSize = this.minHeap.size();if (maxHeapSize + minHeapSize == 0) {return null;}Integer maxHeapHead = this.maxHeap.peek();Integer minHeapHead = this.minHeap.peek();//表示如果兩個(gè)size相同，返回true，所以中位數(shù)是兩個(gè)堆頂元素和的一半。if (((maxHeapSize + minHeapSize) & 1) == 0) {return (maxHeapHead + minHeapHead) / 2;}return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;}}public static class MaxHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {if (o2 > o1) {return 1;} else {return -1;}}}public static class MinHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {if (o2 < o1) {return 1;} else {return -1;}}}// for testpublic static int[] getRandomArray(int maxLen, int maxValue) {int[] res = new int[(int) (Math.random() * maxLen) + 1];for (int i = 0; i != res.length; i++) {res[i] = (int) (Math.random() * maxValue);}return res;}// for test, this method is ineffective but absolutely rightpublic static int getMedianOfArray(int[] arr) {int[] newArr = Arrays.copyOf(arr, arr.length);Arrays.sort(newArr);int mid = (newArr.length - 1) / 2;if ((newArr.length & 1) == 0) {return (newArr[mid] + newArr[mid + 1]) / 2;} else {return newArr[mid];}}public static void printArray(int[] arr) {for (int i = 0; i != arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {boolean err = false;int testTimes = 200000;for (int i = 0; i != testTimes; i++) {int len = 30;int maxValue = 1000;int[] arr = getRandomArray(len, maxValue);MedianHolder medianHold = new MedianHolder();for (int j = 0; j != arr.length; j++) {medianHold.addNumber(arr[j]);}if (medianHold.getMedian() != getMedianOfArray(arr)) {err = true;printArray(arr);break;}}System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");}}

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法之字符凭拼接最低字典序和数据流中取中位数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。