Java日记2018-05-13

第一题 最小的 K 个数
可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字；
Partition 来源于快速排序思想.
观察快速排序是把全部数组排序，当前值需要前k个就行，所以加上对于index与k的判断，只要前k个

package com.lyc.dataautest;



    
    
    public static int partion2(int[] arr,int start,int end) {
        if(arr==null&&start>end) return -1;

        int res = arr[start];
        while(start<end) {
            while(start<end&&arr[end] >= res) {
                end--;
            }
            arr[start] = arr[end];
            while(start<end && arr[start]<res) {
                start++;
            }
            arr[end] = arr[start];
        }
        
        //初始值给与当前最左边的数字，使得当前数组所有数字包含原数组
        arr[start] = res;

        return start;
    }
    public static int[] getLeastNumbers2(int[] input, int k) {
    
        if (input.length == 0 || k <= 0)
            return null;
        int[] output = new int[k];
        int start = 0;
        int end = input.length - 1;
        int index = partion2(input, start, end);
        
        while(index != k - 1) {
            if(index>k-1) {
                end = index-1;
                index = partion2(input, start, end);
            } else {
                start = index+1;
                index = partion2(input, start, end);
            }
            
        }
        
        for (int i = 0; i < k; i++) {
            output[i] = input[i];
            System.out.print(output[i] + " ");
        }
        // System.out.println("end print2");
        return output;
    }

    
    //快速排序
    public static void sort_fast(int[] arr,int left,int right) {
        if(left>right) return;
        
        int i= partion2(arr,left,right);
        sort_fast(arr,left,i-1);
        sort_fast(arr,i+1,right);
        
    }
    public static void main(String[] args) {
        int[] arr = { 4, 5, 1, 6, 2, 7, 3, 8 };
        //getLeastNumbers2(arr, 4);
        sort_fast(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        
    }

}

第二题 数据流中的中位数
参考 https://blog.csdn.net/u011080472/article/details/51291089

考虑将数据序列从中间开始分为两个部分，左边部分使用大根堆表示，右边部分使用小根堆存储。每遍历一个数据，计数器count增加1，当count是偶数时，将数据插入小根堆；当count是奇数时，将数据插入大根堆。当所有数据遍历插入完成后（时间复杂度为O(logn)O(logn)，如果count最后为偶数，则中位数为大根堆堆顶元素和小根堆堆顶元素和的一半；如果count最后为奇数，则中位数为小根堆堆顶元素。

下午重来

public class Solution {
    // 大顶堆，存储左半边元素
    private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
    // 小顶堆，存储右半边元素，并且右半边元素都大于左半边
    private PriorityQueue<Integer> right = new PriorityQueue<>();
    // 当前数据流读入的元素个数
    private int N = 0;

    public void Insert(Integer val) {
        // 插入要保证两个堆存于平衡状态
        if (N % 2 == 0) {
            // N 为偶数的情况下插入到右半边。
            // 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
            // 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边
            left.add(val);
            right.add(left.poll());
        } else {
            right.add(val);
            left.add(right.poll());
        }
        N++;
    }

    public Double GetMedian() {
        if (N % 2 == 0)
            return (left.peek() + right.peek()) / 2.0;
        else
            return (double) right.peek();
    }
}

第三题 字符流中第一个不重复的字符

因为一个字符不会超过8位，所以创建一个大小为256的整形数组，创建一个List，存放只出现一次的字符。insert时先对该字符所在数组位置数量+1，再判断该位置的值是否为1，如果为1，就添加到List中，不为1，则表示该字符已出现不止1次，然后从List中移除，取出时先判断List的size是否为0，不为0直接List.get(0)，就可以得到结果，否则返回‘#’

package com.lyc.dataautest;

import java.util.ArrayList;

public class FirstAppearingOnce {
    private int[] chaCnt = new int[256];
    private ArrayList<Character> lst = new ArrayList<Character>();

    public void insertchar(char ch) {
        chaCnt[ch]++;
        if (chaCnt[ch] == 1) {
            lst.add(ch);
        } else {
            // 当前的数组是否已经有重复的删除，注意要将Character奉上
            lst.remove((Character)ch);
        }
    }

    public char findFist() {
        if (lst.size() == 0) {
            return '#';
        } else {

            return lst.get(0);
        }
    }

    public static void main(String[] args) {
        StringBuffer stb = new StringBuffer("google");
        FirstAppearingOnce fao = new FirstAppearingOnce();
        for (int i = 0; i < stb.length() - 1; i++) {
            fao.insertchar(stb.charAt(i));
        }

        for (int i = 0; i < fao.lst.size() - 1; i++) {
            System.out.println(fao.lst.get(i));
        }

        System.out.println(fao.findFist());
    }

}

第四题 连续子数组的最大和

首先想到用动态规划算法，设置两个变量，一个currentMax用来记录数组相加之和，一个sumMax用来记录最大的子数组和，一旦currentMax大于sumMax，就更新sumMax使它等于currentMax；初始值都赋予数组的第一个元素的值；
那么问题来了，为什么最大的子数组为0来作为判断，为啥不能是1，哥没想太明白，迷迷糊糊懂……

package com.lyc.dataautest;

public class FindGreatestSumOfSubArray {
    public static int findmax(int[] arr) {
        if(arr==null) return 0;
        int cmax=arr[0];
        int res = arr[0];
        //注意循环从i=1开始
        for(int i=1;i<arr.length;i++) {
            if(cmax<0) {
                cmax=arr[i];
            } else {
                cmax+=arr[i];
            }
            if(cmax>res) {
                res = cmax;
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        int[] arr={6,-3,-2,7,-15,1,2,2};
        int te = findmax(arr);
        System.out.println("the res is:"+te);
    }

}