中位数

[编程题]中位数

热度指数：15058 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

中位数定义：一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）. 给出一组无序整数，求出中位数，如果求最中间两个数的平均数，向下取整即可（不需要使用浮点数）

输入描述:

该程序包含多组测试数据，每一组测试数据的第一行为N，代表该组测试数据包含的数据个数，1<=N<=10000.
接着N行为N个数据的输入，N=0时结束输入

输出描述:

输出中位数，每一组测试数据输出一行

示例1

输入

输出

25
40
2

算法知识视频讲解

Java

早豆浆晚牛奶

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            if (n == 0) break;
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(br.readLine());
            }
            Arrays.sort(nums);
            if (n % 2 == 0) System.out.println((nums[n / 2 - 1] + nums[n / 2]) / 2);
            else System.out.println(nums[n / 2]);
        }

    }
}

发表于 2021-04-25 15:10:42 回复(0)

Java

LHC0512

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i]=scanner.nextInt();
            Arrays.sort(a);
            int len =a.length;
            if (len%2==0) System.out.println((a[len/2-1]+a[len/2])/2);
            else System.out.println(a[(len-1)/2]);
        }
    }
}

发表于 2020-03-18 17:29:40 回复(0)

Java

/xinCupid☆

有2种解法，第1种是先排序，再取中间位置的数。第2种是用堆，最大堆存的是最小的前1/2数，直接取堆首的第一或第二个数即可

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        while (reader.hasNext()) {
            int N = reader.nextInt();
            if (N == 0)
                return;
            int size = N/2+1;
            PriorityQueue<Integer>  pq = new PriorityQueue<>(N / 2 + 1, (o1, o2) -> o2 - o1);
            for (int i = 0; i < N; ++i) {
                int number = reader.nextInt();
                if (pq.size() < size) {
                    pq.offer(number);
                } else {
                    if (pq.peek() > number) {
                        pq.poll();
                        pq.offer(number);
                    }
                }
            }
            size = N % 2 == 0 ? 2 : 1;
            int sum = 0;
            for (int i = 0; i < size; ++i) {
                sum += pq.peek();
                pq.poll();
            }
            System.out.println(sum/size);
        }
    }
}

发表于 2018-04-06 00:04:25 回复(0)

Java

涛仔

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner; public class Main {
	
	public int doSome(int[] ints){
		Arrays.sort(ints);
		if(ints.length%2!=0){
			return ints[ints.length/2];
		}else{
			return (ints[ints.length/2-1]+ints[ints.length/2])/2;
		}
	}

	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		Main m=new Main();
		int size;
		while(true){
			size=s.nextInt();
			if(size==0){
				break;
			}
			int[] arrs=new int[size];
			for(int i=0;i<size;i++){
				arrs[i]=s.nextInt();
			}
			System.out.println(m.doSome(arrs));
		}
	}
}

发表于 2017-06-04 21:36:32 回复(0)

Java

哈哈哈牛马

import java.util.ArrayList;
import java.util.Scanner;

/*
 *	QQ:	825580813(一起来敲代码)
 *	思路:
 *		1, 根据快速排序的思想
 *		2, 快速排序过程中有一个步骤为partition的过程,这个过程会返回一个当前调整到的位置
 *		3, 根据数组的个数确定中位数的位置
 *		4, 然后使用partition调整确保中位数位置上的数一定为中位数.
 */
public class Main{
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n;
		while ((n = sc.nextInt()) != 0) {
			ArrayList<Integer> arr = new ArrayList<>();
			for (int i = 0; i < n; ++i) {
				arr.add(sc.nextInt());
			}
			int median = getMedian(arr);
			System.out.println(median);
		}
		sc.close();
	}
	
	private static int getMedian(ArrayList<Integer> arr) {
		if ((arr.size() & 1) == 1) {
			int index = arr.size() / 2;
			quickGetMedian(arr, 0, arr.size() - 1, index);
			return arr.get(index);
		}
		int right = arr.size() / 2;
		int left = right - 1;
		quickGetMedian(arr, 0, arr.size() - 1, left);
		quickGetMedian(arr, 0, arr.size() - 1, right);
		return (arr.get(left) + arr.get(right)) / 2;
	}
	
	private static void quickGetMedian(ArrayList<Integer> arr, int left, int right,
					int aim) {
		if (left < right) {
			int mid = partition(arr, left, right);
			if (mid == aim) {
				return;
			}
			else if (mid > aim) {
				quickGetMedian(arr, left, mid - 1, aim);
			}
			else {
				quickGetMedian(arr, mid + 1, right, aim);
			}
		}
	}

	private static int partition(ArrayList<Integer> arr, int left, int right) {
		int mid = left;
		for (int i = left; i < right; ++i) {
			if (arr.get(i) <= arr.get(right)) {
				swap(arr, mid, i);
				mid++;
			}
		}
		swap(arr, mid, right);
		return mid;
	}

	private static void swap(ArrayList<Integer> arr, int i, int j) {
		int temp = arr.get(i);
		arr.set(i, arr.get(j));
		arr.set(j, temp);
	}
	
}

发表于 2017-06-01 23:43:26 回复(0)