Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
714 views
in Technique[技术] by (71.8m points)

algorithm - Median of Medians in Java

I am trying to implement Median of Medians in Java for a method like this:

Select(Comparable[] list, int pos, int colSize, int colMed)
  • list is a list of values of which to find a specified position
  • pos is the specified position
  • colSize is the size of the columns that I create in the first stage
  • colMed is the position in those columns that I use as the medX

I am not sure which sorting algorithm would be the best to use or how to implement this exactly..

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I don't know if you still need this problem solved, but http://www.ics.uci.edu/~eppstein/161/960130.html has an algorithm:

select(L,k)
{
    if (L has 10 or fewer elements)
    {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    partition L into L1<M, L2=M, L3>M
    if (k <= length(L1))
        return select(L1,k)
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))
    else return M
}

Good luck!


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...