public class MidNum{
public static void main(String args[]){
int[] a=new int[]{3,5,2,3,5,9};
int mid=a[0];
int mid_left=-1;
int mid_right=-1;
for(int i=1;i<a.length;i++){
if(a[i]>mid&&i%2==0){//奇数个且大于
if(a[i]<mid_right){
mid_left=mid;
mid=a[i];
}else{
mid_left=mid;
mid=mid_right;
mid_right=a[i];
}
}else if(a[i]<mid&&i%2!=0){//偶数个且小于
if(a[i]>mid_left){
mid_right=mid;
mid=a[i];
}else{
mid_right=mid;
mid=mid_left;
mid_left=a[i];
}
}else if(a[i]<mid&&i%2==0){//奇数个且小于
//mid=a[i];
if(mid_left==-1)mid_left=a[i];
if(a[i]>mid_left)
mid_left=a[i];
}else if(a[i]>mid&&i%2!=0){//偶数个且大于
//mid=a[i];
if(mid_right==-1)mid_right=a[i];
if(a[i]<mid_right)
mid_right=a[i];
}else if(a[i]==mid){
mid_right=a[i];
}
System.out.println("mid_left:"+mid_left+" midNum:"+mid+" mid_right:"+mid_right);
}
System.out.println("midNum:"+mid);
}
}
19 个解决方案
#1
先排序后取中呗。
#2
排序的复杂度有没有比o(n)更快的?求中位数并不需要把数组排序,只需要将中间值找到即可,这个算法就是避免了多余的排序操作
#3
运行了一下 算法是错的 {3,5,2,3,5,9,1,2,11,12,13} 最后返回11(应该是5)。
#4
关注。。。
#5
gz
#6
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class MidNumber {
public static void main(String args[]){
int[] a= new int[]{1,1,2,2,8,6,9,5,7,10,4,3,6,49,30,29,6,4,98,56,25,47};
HashSet<Integer> b =new HashSet<Integer> ();
for(int temp:a){
b.add((int)temp);
}
List<Integer> f =new ArrayList<Integer>();
f.addAll(b);
Collections.sort(f);
for(Integer temp:f)
System.out.println(temp);
int size=f.size();
boolean num=(boolean)(size%2==0);
System.out.println(num?(f.get((size-1)/2)+" "+f.get((size+1)/2)):(f.get((size-1)/2)));
}
}
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class MidNumber {
public static void main(String args[]){
int[] a= new int[]{1,1,2,2,8,6,9,5,7,10,4,3,6,49,30,29,6,4,98,56,25,47};
HashSet<Integer> b =new HashSet<Integer> ();
for(int temp:a){
b.add((int)temp);
}
List<Integer> f =new ArrayList<Integer>();
f.addAll(b);
Collections.sort(f);
for(Integer temp:f)
System.out.println(temp);
int size=f.size();
boolean num=(boolean)(size%2==0);
System.out.println(num?(f.get((size-1)/2)+" "+f.get((size+1)/2)):(f.get((size-1)/2)));
}
}
#7
像这种无续数组,用分治的思想应该比较高效
#8
多谢各位积极发言,本人现以发现此算法确实是错的,望高人指点,可以在不排序的情况下求出中位数,继续关注。。。。
#9
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = avg - (double)array[0]; //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
自己想了一个不用排序的,但复杂度也不小
#10
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
有地方写错了,现改为:限制temp的值为正
#11
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
有地方写错了,现改为:限制temp的值为正
#12
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
有地方写错了,现改为:限制temp的值为正
#13
网络没响应,多按了几下,发多了,不好意思,我的错,请大家原谅
#14
谢谢12楼发表自己的想法,但是算法也是有问题的
int[]array = {1,2,4,3,5,6};
用这个测试,返回4,实际应该返回3,继续探索中。。。
int[]array = {1,2,4,3,5,6};
用这个测试,返回4,实际应该返回3,继续探索中。。。
#15
是我没看懂题目,还是怎么回事,求中位数,如为奇数不就是返回下标为(a.length-1)/2的数嘛,如为偶数就返回两个,一个a.length/2-1和a.length/2
#16
(1)求中位数要将一组数据按大小顺序,而不必计算,顾名思义,中位数就是位置处于最中间的一个数(或最中间的两个数的平均数),排序时,从小到大或从大到小都可以.
(2)在数据个数为奇数的情况下,中位数是这组数据中的一个数据;但在数据个数为偶数的情况下,其中位数是最中间两个数据的平均数,它不一定与这组数据中的某个数据相等.
在同一组数据中,众数、中位数和平均数也各有其特性:
(1)中位数与平均数是唯一存在的,而众数是不唯一的;
(2)众数、中位数和平均数在一般情况下是各不相等,但在特殊情况下也可能相等。
(2)在数据个数为奇数的情况下,中位数是这组数据中的一个数据;但在数据个数为偶数的情况下,其中位数是最中间两个数据的平均数,它不一定与这组数据中的某个数据相等.
在同一组数据中,众数、中位数和平均数也各有其特性:
(1)中位数与平均数是唯一存在的,而众数是不唯一的;
(2)众数、中位数和平均数在一般情况下是各不相等,但在特殊情况下也可能相等。
#17
无需数列总得先排序吧,那最好的情况(sorted)复杂度也要θ(n)。这几乎不可能发生。
难道可以不排序就得到中间数?
难道可以不排序就得到中间数?
#18
根据中位数的准确概念以及12楼的算法,修改得出以下算法,如发现错误请指出以便改正
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = array[0]; //用于存放中间值
int pivot1 = array[0];
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 1; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k < temp||(Math.abs(k-temp)<0.001)){
pivot1=pivot;
pivot = array[i];
temp = k;
}
System.out.println(i+" p,p1:"+pivot+","+pivot1+"k:"+k);
}
if(array.length%2==0){
System.out.println("p,p1:"+pivot+","+pivot1);
double tt=((double)pivot+pivot1)/2;
System.out.println(tt);
}else{
System.out.println(pivot);
}
}
}
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = array[0]; //用于存放中间值
int pivot1 = array[0];
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 1; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k < temp||(Math.abs(k-temp)<0.001)){
pivot1=pivot;
pivot = array[i];
temp = k;
}
System.out.println(i+" p,p1:"+pivot+","+pivot1+"k:"+k);
}
if(array.length%2==0){
System.out.println("p,p1:"+pivot+","+pivot1);
double tt=((double)pivot+pivot1)/2;
System.out.println(tt);
}else{
System.out.println(pivot);
}
}
}
#19
楼上的同志,貌似数组为1,2,3,4,100你的算法结果就不对。。。
#20
#1
先排序后取中呗。
#2
排序的复杂度有没有比o(n)更快的?求中位数并不需要把数组排序,只需要将中间值找到即可,这个算法就是避免了多余的排序操作
#3
运行了一下 算法是错的 {3,5,2,3,5,9,1,2,11,12,13} 最后返回11(应该是5)。
#4
关注。。。
#5
gz
#6
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class MidNumber {
public static void main(String args[]){
int[] a= new int[]{1,1,2,2,8,6,9,5,7,10,4,3,6,49,30,29,6,4,98,56,25,47};
HashSet<Integer> b =new HashSet<Integer> ();
for(int temp:a){
b.add((int)temp);
}
List<Integer> f =new ArrayList<Integer>();
f.addAll(b);
Collections.sort(f);
for(Integer temp:f)
System.out.println(temp);
int size=f.size();
boolean num=(boolean)(size%2==0);
System.out.println(num?(f.get((size-1)/2)+" "+f.get((size+1)/2)):(f.get((size-1)/2)));
}
}
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class MidNumber {
public static void main(String args[]){
int[] a= new int[]{1,1,2,2,8,6,9,5,7,10,4,3,6,49,30,29,6,4,98,56,25,47};
HashSet<Integer> b =new HashSet<Integer> ();
for(int temp:a){
b.add((int)temp);
}
List<Integer> f =new ArrayList<Integer>();
f.addAll(b);
Collections.sort(f);
for(Integer temp:f)
System.out.println(temp);
int size=f.size();
boolean num=(boolean)(size%2==0);
System.out.println(num?(f.get((size-1)/2)+" "+f.get((size+1)/2)):(f.get((size-1)/2)));
}
}
#7
像这种无续数组,用分治的思想应该比较高效
#8
多谢各位积极发言,本人现以发现此算法确实是错的,望高人指点,可以在不排序的情况下求出中位数,继续关注。。。。
#9
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = avg - (double)array[0]; //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
自己想了一个不用排序的,但复杂度也不小
#10
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
有地方写错了,现改为:限制temp的值为正
#11
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
有地方写错了,现改为:限制temp的值为正
#12
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = 0; //用于存放中间值
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 0; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k == 0){
pivot = array[i];
break;
}
if(k < temp){
pivot = array[i];
temp = k;
}
}
System.out.println(pivot);
}
}
有地方写错了,现改为:限制temp的值为正
#13
网络没响应,多按了几下,发多了,不好意思,我的错,请大家原谅
#14
谢谢12楼发表自己的想法,但是算法也是有问题的
int[]array = {1,2,4,3,5,6};
用这个测试,返回4,实际应该返回3,继续探索中。。。
int[]array = {1,2,4,3,5,6};
用这个测试,返回4,实际应该返回3,继续探索中。。。
#15
是我没看懂题目,还是怎么回事,求中位数,如为奇数不就是返回下标为(a.length-1)/2的数嘛,如为偶数就返回两个,一个a.length/2-1和a.length/2
#16
(1)求中位数要将一组数据按大小顺序,而不必计算,顾名思义,中位数就是位置处于最中间的一个数(或最中间的两个数的平均数),排序时,从小到大或从大到小都可以.
(2)在数据个数为奇数的情况下,中位数是这组数据中的一个数据;但在数据个数为偶数的情况下,其中位数是最中间两个数据的平均数,它不一定与这组数据中的某个数据相等.
在同一组数据中,众数、中位数和平均数也各有其特性:
(1)中位数与平均数是唯一存在的,而众数是不唯一的;
(2)众数、中位数和平均数在一般情况下是各不相等,但在特殊情况下也可能相等。
(2)在数据个数为奇数的情况下,中位数是这组数据中的一个数据;但在数据个数为偶数的情况下,其中位数是最中间两个数据的平均数,它不一定与这组数据中的某个数据相等.
在同一组数据中,众数、中位数和平均数也各有其特性:
(1)中位数与平均数是唯一存在的,而众数是不唯一的;
(2)众数、中位数和平均数在一般情况下是各不相等,但在特殊情况下也可能相等。
#17
无需数列总得先排序吧,那最好的情况(sorted)复杂度也要θ(n)。这几乎不可能发生。
难道可以不排序就得到中间数?
难道可以不排序就得到中间数?
#18
根据中位数的准确概念以及12楼的算法,修改得出以下算法,如发现错误请指出以便改正
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = array[0]; //用于存放中间值
int pivot1 = array[0];
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 1; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k < temp||(Math.abs(k-temp)<0.001)){
pivot1=pivot;
pivot = array[i];
temp = k;
}
System.out.println(i+" p,p1:"+pivot+","+pivot1+"k:"+k);
}
if(array.length%2==0){
System.out.println("p,p1:"+pivot+","+pivot1);
double tt=((double)pivot+pivot1)/2;
System.out.println(tt);
}else{
System.out.println(pivot);
}
}
}
public class AAA {
public static void main(String[]args){
int[]array = {3,5,2,3,5,9,1,2,11,12,13};
int n = 0; //存放数组元素之和
for(int i = 0; i < array.length; i++){
n += array[i];
}
double avg = (((double)n)/((double)array.length)); //求得数组元素的平均数
double k = 0; //用于存放平均数与单个数组元素的差值
int pivot = array[0]; //用于存放中间值
int pivot1 = array[0];
double temp = Math.abs(avg - (double)array[0]); //用于与K值比较
for(int i = 1; i < array.length; i++){
k = Math.abs(avg-array[i]);
if(k < temp||(Math.abs(k-temp)<0.001)){
pivot1=pivot;
pivot = array[i];
temp = k;
}
System.out.println(i+" p,p1:"+pivot+","+pivot1+"k:"+k);
}
if(array.length%2==0){
System.out.println("p,p1:"+pivot+","+pivot1);
double tt=((double)pivot+pivot1)/2;
System.out.println(tt);
}else{
System.out.println(pivot);
}
}
}
#19
楼上的同志,貌似数组为1,2,3,4,100你的算法结果就不对。。。