大家看一笔试题

Question

我同学笔试的时候出的。我没做出来。
给一个数组a[n] n可以为任意奇数，但是数组中的数都是0-99之间的数，现在要求最多只遍历数组一次，找出数组中大小处于数组中间的那个数。
注意：该中间的数可能在数组中不止出现一次
比如a[n]={2,8,88,33,66,54,54,99,88}; 排序后是{2,8,33,54,54,66,88,88,99},那么结果就使索引为4的那个数 即54

Answer 1

规定只能遍历一次，但是没有规定另开空间，重新申请一个数组b[n]，遍历a[n]一遍以后可以将里面的数据用插入法有序插到b[n]中，目前就想到这么个笨办法，等高人

Answer 2

给一个数组a[n] n可以为任意奇数 。那么数组中间的数就是 a[（n/2）+1]，
首先对数组a[n]遍历一次取 a[（n/2）+1]的值，然后用 a[n/2]和a[(n/2)+1]进行比较，相等继续用a[(n/2)]和a[(n/2)-1]比较，直到不相等则终止比较输出结果。

Answer 3

三个临时变量叫L,M,H,吧，取的两个数叫A，B，吧。AB和中间的M比，如果都小于M的话：L，M，右移至M，H，然后L放A和B中大的那个。如果AB都大于M则相反。如果一个大于一个小于，（按A＞B说吧）。则更新L和H，L放L和B中大的，H放H和A中小的。这样一直到取完直接返回M就行了

Answer 4

既然是奇数个  先排序  取中位数a[i]
然后数列求和 取平均数 
比较a[i-1],a[i]与平均数的差 确定遍历方向
差最小的即是

Answer 5

来种不负责任的算法:遍历一个就把它放到一个HashSet 里面,遍历完了由HashSet得到 Iterator .遍历得到里面的第 n/2+1 个元素就是中间数了  - -

Answer 6

错了,是TreeSet   - -!

Answer 7

错了,是TreeSet   - -!

Answer 8

public class Test23 {
public static void main(String[] args) {
int[] an = {2, 8, 88, 33, 66, 54, 54, 99, 88};
System.out.println(mid(an));
}
public static int mid(int[] an) {
if(an.length % 2 == 0) { //数组长度不是奇数，不考虑了，下面是一次取两个，这里是防止出异常。
return 0;
} else if(an.length == 1) { //只有一个数。
return an[0];
}
int m = an[0];
int l = 0;
int h = 0;
int a = an[1];
int b = an[2];
if(an[1] > an[2]) {
a = an[2];
b = an[1];
} else {
a = an[1];
b = an[2];
}

//处理前三个数
if(a >= m) {
l = m;
m = a;
h = b;
} else if(b <= m) {
h = m;
m = b;
l = a;
} else {
l = a;
h = b;
}

//两个两个取出并处理
for(int i = 3; i < an.length; i += 2) {
if(an[i] > an[i+1]) {
a = an[i+1];
b = an[i];
} else {
a = an[i];
b = an[i+1];
}
if(a >= m ) {
l = m;
m = a < h ? a : h;
h = b < h ? b : h;
} else if(b <= m) {
h = m;
m = b > l ? b : l;
l = a > l ? a : l;
} else {
l = a > l ? a : l;
h = b < h ? b : h;
}
}
return m;
}
}代码只写了方法，没写测试，测试自己写吧，随机生成199个0-99的数（必有重复了）。然后调用这个方法

Answer 9

方法有错误，晚上再修改，错误是:a >= m 或b <= m时，m中放的数和h(l)放的数不对，应该三个数比较，或者分成五种情况处理

Answer 10

public class Test23 {
public static void main(String[] args) {
int[] an = {2, 8, 88, 33, 66, 54, 54, 99, 88};
System.out.println(mid(an));
}
public static int mid(int[] an) {
if(an.length % 2 == 0) { //数组长度不是奇数，不考虑了，下面是一次取两个，这里是防止出异常。
return 0;
} else if(an.length == 1) { //只有一个数。
return an[0];
}
int m = an[0];
int l = 0;
int h = 0;
int a = an[1];
int b = an[2];
if(an[1] > an[2]) {
a = an[2];
b = an[1];
} else {
a = an[1];
b = an[2];
}

//处理前三个数
if(a >= m) {
l = m;
m = a;
h = b;
} else if(b <= m) {
h = m;
m = b;
l = a;
} else {
l = a;
h = b;
}

//两个两个取出并处理
for(int i = 3; i < an.length; i += 2) {
if(an[i] > an[i+1]) {
a = an[i+1];
b = an[i];
} else {
a = an[i];
b = an[i+1];
}
if(a >= m ) {
l = m;
m = a < h ? a : h;
h = b < h ? b : (a < h ? h : a);
} else if(b <= m) {
h = m;
m = b > l ? b : l;
l = a > l ? a : (b > l ? l : b);
} else {
l = a > l ? a : l;
h = b < h ? b : h;
}
}
return m;
}
}

Answer 11

public static int medInArray(int[] arr) {
int med = arr[arr.length/2+1];
int sum = arr[arr.length/2+1];
for(int i=0; i<arr.length; i++) {
if(i < arr.length/2) {
sum += arr[i] + arr[arr.length-1-i];
} else {
if(Math.abs(arr[i]*arr.length - sum) < Math.abs(med*arr.length - sum)) {
med = arr[i];
}
if(Math.abs(arr[arr.length-1-i]*arr.length - sum) < Math.abs(med*arr.length - sum)) {
med = arr[arr.length-1-i];
}
}
}
return med;
}
应该算是遍历一次吧，没有测试

Answer 12

和我今天在论坛看过的题好像一样的！
a[n]={2,8,88,33,66,54,54,99,88};
b[n]=Arrays.sort(a[n].clone())
int result=b[(n-1)/2]

Answer 13

//桶排序算法public static int getMidIndex(int[] array){
int[] b =new int[100];
Vector<Integer> vector = new Vector<Integer>();
//遍历数组
for(int j = 0;j<array.length;j++ ){
//排序后是{2,8,33,54,54,66,88,88,99},那么结果就使索引为4的那个数
//是靠后的那个数所以可以覆盖b[array[i]]；
//
b[array[j]]=j;
}
for(int i =0;i<b.length;i++){
if(0!=b[i]){
vector.addElement(b[i]);
}
}
// 给一个数组a[n] n可以为任意奇数，
return vector.elementAt(vector.size()/2);
}

public static void main(String[] args) {
int b[]= {2,8,88,33,66,54,54,99,88};
//int b[]= {2,8,88,33,66,54,54,99,88,34,43};
System.out.println(getMidIndex(b));
}

Answer 14

//但是数组中的数都是0-99之间的数
 int[] b =new int[100];

Answer 15

public class test { public static int a(int[] arr){
int rs=0;
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-1;j++){
if(arr[j]>arr[j+1]){
arr[j]=arr[j]^arr[j+1];
arr[j+1]=arr[j+1]^arr[j];
arr[j]=arr[j]^arr[j+1];
}
}
}
rs=arr[(arr.length-1)/2];
return rs;
}

public static void main(String[] args) {
int arr[]={2,8,88,33,66,54,54,99,88};
System.out.println(test.a(arr));
}}
不对请大家纠正哈  呵呵 

Answer 16

不好意思没仔细测试
有个 小BUG基本思想是 采用桶装排序 public static int getMidIndex(int[] array){
//    给一个数组a[n] n可以为任意奇数，但是数组中的数都是0-99之间的数，
int[] b =new int[100];
Vector<Integer> vector = new Vector<Integer>();
//遍历数组
for(int j = 0;j<array.length;j++ ){
//排序后是{2,8,33,54,54,54,54,66,88,88,99},那么结果就使索引为4的那个数
//是靠后的那个数所以可以覆盖b[array[i]]；
//
b[array[j]]=j;
}
for(int i =0;i<b.length;i++){
if(0!=b[i]){
vector.addElement(b[i]);
}
}
//是靠后的那个数所以可以覆盖b[array[i]]；这里修改下 return vector.size()%2==0?vector.elementAt(vector.size()/2-1):vector.elementAt(vector.size()/2);
}

public static void main(String[] args) {
int b[]= {2,8,88,33,66,54,54,99,88};
//int b[]= {2,8,88,33,66,54,54,99,88,34,43};
System.out.println(getMidIndex(b));
}

Answer 17

还是有BUG我想了 下如果 int b[]= {2,8,88,33,66,54,54,99,88};return vector.size()%2==0?vector.elementAt(vector.size()/2-1):vector.elementAt(vector.size()/2);
这理还是有错误
桶中的数字
只有偶数种值（0－99除掉重复的）即（24，43，56，78）不好判断中间的两个数字43 出现多（return vector.elementAt(vector.size()/2-1)）还是65出现多（vector.elementAt(vector.size()/2):），谁出现的次数多应该返回 
搞了半天了看来考虑还是不够全面啊 谢谢26楼的提醒
public static int getMidIndex(int[] array){
int[] b =new int[100];
int[] bcopy = new int[100];
Vector<Integer> vector = new Vector<Integer>();
//标志位
Vector<Integer> vectorcopy = new Vector<Integer>();

//遍历数组
for(int j = 0;j<array.length;j++ ){
//排序后是{2,8,33,54,54,54,54,66,88,88,99},那么结果就使索引为4的那个数
//是靠后的那个数所以可以覆盖b[array[i]]；
//证明b[array[j]]已经存在需要替换
if(b[array[j]]!=0){
bcopy[array[j]]++;
}
b[array[j]]=j;

}
for(int i =0;i<b.length;i++){
if(0!=b[i]){
vector.addElement(b[i]);
//对应的重复次数2个相同为1次
vectorcopy.addElement(bcopy[i]);
}
} int front = vector.elementAt(vector.size()/2-1);
int back = vector.elementAt(vector.size()/2);
//如果桶中的值为偶数种根据copy标志位判断取谁；
if(vector.size()%2==0){
return vectorcopy.elementAt(vector.size()/2-1)>vectorcopy.elementAt(vector.size()/2)?front:back;
}
return vector.elementAt(vector.size()/2);

}

public static void main(String[] args) {
int b[]= {2,8,88,33,66,54,54,99,88};
//int b[]= {2,8,88,33,66,54,54,99,88,34,43};
System.out.println(getMidIndex(b));
}

Answer 18

public static void main(String args[])
{
int a[]={2,8,88,33,66,54,54,99,88};//初始化数组
ArrayList<Integer> list = new ArrayList<Integer>();
int b[] = new int[a.length];
b[0]=a[0];
/*
 * 遍历一次数组
 */
for(int i=1;i<a.length;i++)
{
int j=0;
int k = a[i];
if(!list.contains(a[i]))//排除重复的数字，不重复的数字放入list中
{
list.add(a[i]);
/*
 * 将不重复的数字排序
 */
while(b[j]!=0&&j<b.length-1)
{
int k2=k;
if(b[j]>k)
{
k=b[j];
b[j]=k2;

}
if(j<b.length-1&&b[j+1]==0)
{
b[j+1]=k;
break;
}
j++;
}
}
}

System.out.println(b[list.size()/2]);//输出，排序后最中间的数。当然如果出现2个也就是不重复的是8个那么第4~5个数字应该都是中间数吧？这里只打印第4个

}

Answer 19

给个简单的
/**
 * 给一个数组a[n] n可以为任意奇数，但是数组中的数都是0-99之间的数，现在要求最多只遍历数组一次，找出数组中大小处于数组中间的那个数。 
 *注意：该中间的数可能在数组中不止出现一次 
 *比如a[n]={2,8,88,33,66,54,54,99,88}; 排序后是{2,8,33,54,54,66,88,88,99},那么结果就使索引为4的那个数 即54
 * @author Ydy from Wyu
 *
 */
public class FindMid {
public static int find(int[] a){
int[] temp = new int[100];//既然已经限定范围是0-99，该数组已可满足要求
for(int i=0;i<a.length;i++)
{
temp[a[i]]+=1;//a[i]的值作下标，temp[i]中的值表示数i出现的次数
}
int sum=0;
for(int i=0;i<temp.length;i++){
sum+=temp[i];
if(sum>=a.length/2)//已限定输入数组是奇数个，所以判断较简单
return i;
}
return 0;
}
public static void main(String args[])
{
int[]a={5,23,7};
int[] b={2,8,88,33,66,1,1,54,54,99,88}; 
System.out.println(find(a));
System.out.println(find(b));
}
}

Answer 20

这句话是废话吧,如果去掉重复的数字以后,数组里面元素个数为偶数那怎么办?
比如int[] a = {2,8,88,33,66,55,54,99,88};
不太明白,感觉题目出的有问题.
比较喜欢20楼

Answer 21

我有一个想法，既然n你知道，那么n/2就应该知道，比如n=9那么一半就是5，从第一个开始遍历，另设一个记录变量int i =1和一个int max,起初把第一个数给max，然后往后依次和max比较如果有一个≥max的数字，就把max改变为那个数字，同时把i++,当 i = n/2的时间就停止，这个办法最多遍历依次数组，对不对？至于具体的程序就比较简单了吧！

Answer 22

这么多喜欢20楼的呢，sort是一个装饰者，返回值是void,b[n]=Arrays.sort就已经写错了，最主要的是，谁规定最中间的那个就是正解了？int a[]={1,1,1,2,3}按20楼的做法会出几？

Answer 23

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class test {
  public static void main(String []args){
    int []arr=new int[]{12,32,22,1,55,22,33};
    List arrl=new ArrayList();
    for(int i=0;i<arr.length;i++){
      arrl.add(arr[i]);
    }
    Collections.sort(arrl);
    for(int i=0;i<arrl.size();i++){
      System.out.println(arrl.get(i)+"   ");
    }
    System.out.println("此數為："+arrl.get(arrl.size()/2));
  }
}

Answer 24

按照这个算法，如果是数组int[] a = {1,1,1,1,1,1,1,9,20}会得出什么结果？
找出数组中“大小”处于数组中间的那个数，这个数未必就是组数中间的数吧？
应该是说数组中的一个数，它的大小排在数组中所有数的中间，并不是指它的下标。
我是这么理解的。 

Answer 25

同意，39楼的如果n<99,也就是常熟时间，如果n远远大于99，就是O(n)，已经不错了。至于说空间复杂度，题目中给出的“但是数组中的数都是0-99之间的数”，用意明显。

Answer 26

39楼的有点小问题 呵呵 更正一下
    public static int find(int[] a){
        int[] temp = new int[100];
        for(int i=0;i<a.length;i++)
        {
            temp[a[i]]+=1;
        }
        int sum=0;
        for(int i=0;i<temp.length;i++){
            sum+=temp[i];
            if(sum>=(a.length+1)/2)//这里应该是a.length+1
                return i;
        }
        return 0;
//这个效率应该是最优的。
    }

Answer 27

有个数组类ArrayList有个方法直接排序public <T> T[] toArray(T[] a)按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。如果指定的数组能容纳列表，则将该列表返回此处。否则，将分配一个具有指定数组的运行时类型和此列表大小的新数组。 
如果指定的数组能容纳队列，并有剩余的空间（即数组的元素比队列多），那么会将数组中紧接 collection 尾部的元素设置为 null。（仅 在调用者知道列表中不包含任何 null 元素时才能用此方法确定列表长度）。
排完后只要取出数组中的  （int）（n/2+1）位置上的值就0K了 

Answer 28

我觉得46楼的方法是比较好的！只是最后的循环应该是没用的
         public static int getMiddleNum(int []ia)
{
 List arrl=new ArrayList(); 
    for(int i=0;i <ia.length;i++){ 
      arrl.add(String.valueOf(ia[i])); 
    } 
    Collections.sort(arrl); 
    int m=ia.length/2;
    return Integer.parseInt(arrl.get(m+1).toString()); }
我想这样就可以了

Answer 29

有个数组类ArrayList有个方法直接排序public <T> T[] toArray(T[] a)按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。如果指定的数组能容纳列表，则将该列表返回此处。否则，将分配一个具有指定数组的运行时类型和此列表大小的新数组。 
如果指定的数组能容纳队列，并有剩余的空间（即数组的元素比队列多），那么会将数组中紧接 collection 尾部的元素设置为 null。（仅 在调用者知道列表中不包含任何 null 元素时才能用此方法确定列表长度）。
排完后只要取出数组中的  （int）（n/2+1）位置上的值就0K了 

Answer 30

  修改一下 应该返回 Integer.parseInt(arrl.get(m).toString());  就可以了 

Answer 31

  修改一下 应该返回 Integer.parseInt(arrl.get(m).toString());  就可以了 

Answer 32

谢谢提醒。如果是a.length/2的话。当a[]中有个0出现的时候，结果就不正确了.

Answer 33

class A {
public static void main(String[] args) {
getMinNum(5);
}

public static void getMinNum(int n) {
int[] a = new int[n];
Random r = new Random();
for(int i=0;i<a.length;i++) {
a[i] = r.nextInt(99);
System.out.println(a[i]);
}
System.out.println("----------------------");
Arrays.sort(a);
for(int i=0;i<a.length;i++) {
System.out.println(a[i]);
}
System.out.println("------------------------");
System.out.println(a[(n-1)/2]);
}
}