数据结构与算法之字符凭拼接最低字典序和数据流中取中位数

深碍√TFBOYSˉ_ 2021-12-15 16:39 79阅读 0赞

# 数据结构与算法之字符凭拼接最低字典序和数据流中取中位数 #

--------------------

## 目录 ##

1.  字符凭拼接最低字典序
2.  数据流中取中位数

--------------------

### 1. 字符凭拼接最低字典序 ###

1.  题目描述  
    ![在这里插入图片描述][2019070309385424.png]
2.  思路：
    
    1.  创建一个比较器，比较的内容是`(o1+o2).compareTo(o2+o1)·`，返回的就是两者之和中字典顺序低的那一个。
    2.  在排序时应用比较器，将字符数组进行排序，然后依次组合即可。
3.  代码实现

import java.util.Arrays;
    import java.util.Comparator;
    
    public class Code_05_LowestLexicography {
        
    
    	public static class MyComparator implements Comparator<String> {
        
    		@Override
    		public 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));
    
    	}
    
    }

![在这里插入图片描述][20190703094654425.png]

--------------------

### 2. 数据流中取中位数 ###

1.  题目描述  
    ![在这里插入图片描述][2019070309471958.png]
2.  思路
    
    1.  创建一个大根堆和小根堆，中位数就是两者堆顶元素中的一个，返回即可
    2.  具体思路见代码
3.  代码实现

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());
    
            //调整大根堆和小根堆，两者之元素差=2时，弹出堆顶元素添加到另一个堆
            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. 如果大根堆堆顶元素大于添加元素，则添加到大根堆，否则进行else判断
             * 3. 如果小根堆为null，直接添加到小根堆
             * 4. 如果小根堆堆顶元素大于添加元素，添加元素添加到大根堆，否则加入小根堆
             * 5. 最后要调整大根堆和小根堆的状态
             */
            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();
            }
    
            //返回大根堆和小根堆之间的中位数
            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();
                //表示如果两个size相同，返回true，所以中位数是两个堆顶元素和的一半。
                if (((maxHeapSize + minHeapSize) & 1) == 0) {
        
                    return (maxHeapHead + minHeapHead) / 2;
                }
                return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
            }
    
        }
    
        public static class MaxHeapComparator implements Comparator<Integer> {
        
            @Override
            public int compare(Integer o1, Integer o2) {
        
                if (o2 > o1) {
        
                    return 1;
                } else {
        
                    return -1;
                }
            }
        }
    
        public static class MinHeapComparator implements Comparator<Integer> {
        
            @Override
            public int compare(Integer o1, Integer o2) {
        
                if (o2 < o1) {
        
                    return 1;
                } else {
        
                    return -1;
                }
            }
        }
    
        // for test
        public 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 right
        public 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^_^");
    
        }
    
    }

[2019070309385424.png]: /images/20211215/451c2b4ae7b64327b28530cbe4c2e19f.png
[20190703094654425.png]: /images/20211215/91298ef0668e4f72ad4424fd33b5e7ac.png
[2019070309471958.png]: /images/20211215/f6f8ad4bdcb7452497a0cef62e924840.png