通过使用选择算法中的枢轴来重复 [英] recur by using the pivot in Select algorithm

查看:23
本文介绍了通过使用选择算法中的枢轴来重复的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有一个问题,我无法获取本站点的第 (14,15,16,17) 行用于 Select 算法的目的.

I have a problem and I can not get the purpose of lines (14,15,16,17) of this site for Select algorithm.

有此问题的网站位于 这里.

The site which had this question was located here.

已另外,为使用枢轴分区和递归"部分编写这些行是否正确?(m"是我的主元,i"是这个算法的输入)

EDITED: Also, is this correct to write these lines for the part "partition and recur by using the pivot"? ("m" is my pivot and "i" is the input of this algorithm)

         arrOne<--{a of arr : a<m}
         arrTwo<--{a of arr : a>m}
         if    (i < m ) then
               return Select(arrOne,i)
         else if (i > m)  then
                return Select(arrTwo,i-m)
         else 
                return m

推荐答案

这是它选择要递归的分区的地方.

This is where it selects the partition in which to recurse.

为了说明起见,我们假设您正在寻找具有 100 个元素的数组的中值.第一次分区时,您会得到 60 和 40 个项目的分区.由于您正在寻找第 50 个 项目,您知道它必须位于左侧分区(其中有 60 个项目).

For the sake of illustration, let's assume you're looking for the median of an array with 100 elements. The first time you partition, you get partitions of, say, 60 and 40 items. Since you're looking for the 50th item, you know it must be in the left partition (which has 60 items).

然后您将其分区,并分别得到 25 个和 35 个项目的左右分区.这次我们可以看到第 50th 项必须在正确的分区中,所以我们递归到那个分区.

You then partition that, and get, we'll say, left and right partitions of 25 and 35 items respectively. This time we can see that the 50th item must be in the right partition, so we recurse into that one.

我们继续这样做,直到我们到达一个只包含一个项目的分区——我们正在寻找的那个.

We continue this until we reach a partition that contains only one item -- the one we're looking for.

这篇关于通过使用选择算法中的枢轴来重复的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆