[Interview Questions] Give multiple unordered positive integers, find the median

topic: Give you a lot of positive integers, but they are unordered and find their median.

At the beginning, I wanted to say that I used the fast row. I sorted the integers first, then found the median, but thought that it might not be the answer that the interviewer wanted, so I used other methods and finally did not completely solve it. come out.

[Experience summary: When the interviewer asks an algorithm question, if you can't think of a way to optimize it, let him know the solution that can be thought of, even if this plan may be bad [smile cry], then Consider the next step of optimization, don't always think about finding the best solution, so you may not be able to say it in the end. 】

思维: This method is better to use the heap, create a minimum heap with the first (n+1)/2 numbers of the sequence, then continue to traverse backwards, and each number and the top element For comparison, if it is less than or equal to the top element of the heap, ignore, traverse the next one, if it is larger than the top element of the heap, replace the top element with the element currently traversed, and then re-adjust to the minimum heap. After the traversal is completed, the top element is For the median. The top of the heap is always guaranteed to be the kth small element. After the traversal is completed, the top of the heap becomes the (n+1)/2 small element, which is the median.

码:

public class Mid {

	public static void main(String[] args) {
		
		int[] num = {5,7,6,3,8,1,4};
		int n = getMid(num);
		System.out.println(n);
	}

	private static int getMid(int[] num) {
		int len =(num.length+1)/2;
		for(int i=len/2;i>=0;i--)
			adjustHeap(num,i,len-1);
		System.out.println(Arrays.toString(num));
		
		for (int j = len; j<num.length; j++) {
			if(num[j]>num[0])
			{
				num[0]=num[j];
				adjustHeap(num,0,len-1);
			}
		}
		return num[0];
	}

	private static void adjustHeap(int[] num, int i, int j) {
		int tmp = num[i];
		for (int k = 2*i+1; k <=j; k++) {
			if(k<j&&num[k]>num[k+1])
				k++;
			if(num[k]<tmp)
			{
				num[i]=num[k];
				i=k;
			}else
				break;
		}
		num[i]=tmp;
	}

	private static void swap(int[] num, int i, int j) {
		int tmp=num[i];
		num[i]=num[j];
		num[j]=tmp;
	}
}

出出: