2017年搜狗校招Java研发笔试编程题

最终收敛值

时间限制：C/C++语言 2000MS；其他语言 4000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

假设a[n]是一个有n个元素的整型数组，定义该数组上的一个操作f(a[n],r)，f把a[n]按步长r映射到另外一个数组b[n]，映射规则如下：b[i]=MED(a[i],a[(i+1)mod n],a[(i+2)mod n],...a[(i+r-1)mod n])。MED指中位数，即获得r个元素中从小到大排在中间的元素（如果r是偶数，取中间两个元素较大的那个）。mod n是指模n的加法，相当于a[n]是一个循环数组。

现输入一个数组a[n]，和步长初始值r(1<=r<=n)，用f对数组a[n]进行反复的迭代映射（映射结果写回a[n]），每迭代一轮步长r增加1，直到最后一轮r=n之后迭代结束。此时数组a[n]中每一个元素必然完全相同，请把这个元素输出。

提示：

除了对性能和正确性的要求，我们还将重点考察代码书写风格。

输入

第一行是数组的长度n，第二行是r的初始值，之后n行每行是一个整数，对应a[n]中一个元素。

输出

最终收敛值。

样例输入

7

5

1

2

3

4

5

6

7

样例输出

5

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {
			int n = in.nextInt();
			int r = in.nextInt();
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = in.nextInt();
			}
			while (r <= n) {
				a = doSomething(a, r, n);
				r++;
			}
			System.out.println(a[0]);
		}
	}

	public static int[] doSomething(int[] a, int r, int n) {
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			List<Integer> list = new ArrayList<Integer>();
			int k = i;
			for (int j = 0; j < r; j++) {
				list.add(a[k % n]);
				k++;
			}
			Collections.sort(list);
			b[i] = list.get(r / 2);
		}
		return b;
	}
}
           

AC了20%。。。。