算法-如何不排序判断数组中某个值是否属于前30%的值

Question

举个例子，一个一维数组中有100个无序的数字，任意取一个数，求不排序判断该数字是否属于这个数组中从小到大排列的前30个数

Answer 1

将这个数在该数组中快排一次(假设从小到大)，那么排了一遍后，该数所在的位置就是它最后的位置，如果它的下标<30,那么它就是属于该数组从小到大排序的前30了，时间复杂度O(logN)

Answer 2

能不能建一个百分之三十大小的堆，通过往里面插数据来找出前百分之三十的，如果这个数据连最初的30%都进不去就直接判断小了

Answer 3

如果你遍历一次，算法时间复杂度为O(N)。我感觉这是一道快速排序的变体题，需要快速排序的一个步骤。快速排序的平均时间复杂度为O(N*logN)。你在快速排序完成一个步骤后，就可以知道你的数是否属于前30%的值。

Answer 4

求出一个数组中任意第k大的元素的算法都是O(n)的，类似于快速排序，只不过每次递归只处理一边。找到第30的，然后和第30的比一下大小就行了。

Answer 5

假设 list 为这100个数 m为 要判断的
变量 min_t = 0; max_t = 0 分别用来记录比我小的数目 和比我大的数目

遍历list 原始 和 m比较大小 如果小于m 那么 min_t ++ 否则 max_t++

当min_t >= 30 表示就在 不在前30%(因为已经有30%比我小) 可以停止
或者 max_t >= 70 表示 在前30%(因为已经有70%比我大) 可以停止

通过实际代码测试 基本上 列表每个元素的处理
最坏的情况就是遍历完整个列表 但是实际测试中没有一次是遍历完整个列表的
但是基本不会超过100 或许是我的标本有问题 不过是随机生成的100个数

#!/usr/bin/python
#-*- coding:utf-8 -*-

import random

def test(m=800):
# a 用random.randint(1,10000) 生成的100个数
a = [6076, 8456, 6358, 4798, 5591, 7361, 8526, 7878, 4764, 1187, 6759, 2027, 7293, 4412, 5160, 9292, 3291, 9065, 9662, 6592, 4815, 2051, 5354, 2881, 9166, 5622, 93, 3228, 9460, 9185, 366, 5183, 4225, 2837, 2411, 4102, 1234, 4812, 8450, 9434, 4265, 1919, 5503, 3336, 6931, 6559, 7780, 2956, 8655, 9106, 733, 2998, 8555, 5623, 5321, 3463, 867, 9455, 9682, 807, 4777, 3724, 7942, 7088, 3922, 7746, 7827, 2880, 6943, 5200, 2289, 6502, 212, 6945, 4904, 2481, 7516, 5497, 7812, 2553, 9651, 6165, 8171, 5391, 469, 7517, 9933, 3145, 9644, 4959, 5244, 5311, 1973, 5613, 1186, 9680, 4541, 7628, 7168, 7280]
c = 0
mi = 0
ma = 0

for i in a:
if m < i:
ma += 1
else: mi += 1
c += 1 # 遍历了列表里的一个元素
if mi >= 30:
print '已经有30个比我小 我不是前30小 no'
break
if ma >= 70:
print '已经有70个比我大 不用比我就是前30小 yes'
break
print '总共遍历了列表里的:%d 个元素' % c

if __name__ == '__main__':
for i in xrange(100):
t = random.randint(100,10000)
print '---------%d----------' % (i+1,)
print '测试值为 %d' % t

test(t)

R:>mi.py
---------1----------
测试值为 1622
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------2----------
测试值为 5198
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:61 个元素
---------3----------
测试值为 4051
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:95 个元素
---------4----------
测试值为 8404
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:38 个元素
---------5----------
测试值为 5590
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:56 个元素
---------6----------
测试值为 6154
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:51 个元素
---------7----------
测试值为 3993
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:95 个元素
---------8----------
测试值为 6402
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:48 个元素
---------9----------
测试值为 9485
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:31 个元素
---------10----------
测试值为 9954
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素
---------11----------
测试值为 810
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:75 个元素
---------12----------
测试值为 858
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:75 个元素
---------13----------
测试值为 1103
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:76 个元素
---------14----------
测试值为 5616
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:55 个元素
---------15----------
测试值为 1627
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------16----------
测试值为 3472
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:98 个元素
---------17----------
测试值为 891
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:76 个元素
---------18----------
测试值为 4852
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:65 个元素
---------19----------
测试值为 9191
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:33 个元素
---------20----------
测试值为 2314
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:82 个元素
---------21----------
测试值为 4157
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:93 个元素
---------22----------
测试值为 2162
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:81 个元素
---------23----------
测试值为 8504
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:37 个元素
---------24----------
测试值为 3577
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:98 个元素
---------25----------
测试值为 5188
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:61 个元素
---------26----------
测试值为 3985
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:95 个元素
---------27----------
测试值为 7626
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:41 个元素
---------28----------
测试值为 3251
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:94 个元素
---------29----------
测试值为 692
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------30----------
测试值为 501
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------31----------
测试值为 8074
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:38 个元素
---------32----------
测试值为 2162
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:81 个元素
---------33----------
测试值为 7636
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:41 个元素
---------34----------
测试值为 7952
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:38 个元素
---------35----------
测试值为 8526
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:36 个元素
---------36----------
测试值为 3089
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:91 个元素
---------37----------
测试值为 440
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------38----------
测试值为 2693
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:86 个元素
---------39----------
测试值为 9847
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素
---------40----------
测试值为 1842
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------41----------
测试值为 4700
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:80 个元素
---------42----------
测试值为 2670
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:86 个元素
---------43----------
测试值为 5134
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:65 个元素
---------44----------
测试值为 4858
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:65 个元素
---------45----------
测试值为 8182
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:38 个元素
---------46----------
测试值为 7626
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:41 个元素
---------47----------
测试值为 569
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------48----------
测试值为 5252
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:61 个元素
---------49----------
测试值为 718
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------50----------
测试值为 6736
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:44 个元素
---------51----------
测试值为 760
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:74 个元素
---------52----------
测试值为 5121
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:65 个元素
---------53----------
测试值为 9850
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素
---------54----------
测试值为 4244
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:88 个元素
---------55----------
测试值为 1464
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------56----------
测试值为 4501
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:80 个元素
---------57----------
测试值为 5431
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:57 个元素
---------58----------
测试值为 576
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------59----------
测试值为 1422
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------60----------
测试值为 2096
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:81 个元素
---------61----------
测试值为 1589
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------62----------
测试值为 881
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:76 个元素
---------63----------
测试值为 3923
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:95 个元素
---------64----------
测试值为 7909
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:38 个元素
---------65----------
测试值为 9268
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:33 个元素
---------66----------
测试值为 9745
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素
---------67----------
测试值为 6284
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:51 个元素
---------68----------
测试值为 387
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------69----------
测试值为 1877
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------70----------
测试值为 1642
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------71----------
测试值为 2112
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:81 个元素
---------72----------
测试值为 323
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:71 个元素
---------73----------
测试值为 3026
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:91 个元素
---------74----------
测试值为 4818
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:65 个元素
---------75----------
测试值为 8889
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:36 个元素
---------76----------
测试值为 1069
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:76 个元素
---------77----------
测试值为 9681
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素
---------78----------
测试值为 4365
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:85 个元素
---------79----------
测试值为 6196
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:51 个元素
---------80----------
测试值为 2848
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:87 个元素
---------81----------
测试值为 332
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:71 个元素
---------82----------
测试值为 5774
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:52 个元素
---------83----------
测试值为 9832
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素
---------84----------
测试值为 7534
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:41 个元素
---------85----------
测试值为 5456
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:57 个元素
---------86----------
测试值为 5385
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:57 个元素
---------87----------
测试值为 6256
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:51 个元素
---------88----------
测试值为 6474
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:48 个元素
---------89----------
测试值为 8819
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:36 个元素
---------90----------
测试值为 5787
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:52 个元素
---------91----------
测试值为 936
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:76 个元素
---------92----------
测试值为 4322
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:85 个元素
---------93----------
测试值为 4959
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:65 个元素
---------94----------
测试值为 1569
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:78 个元素
---------95----------
测试值为 6574
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:46 个元素
---------96----------
测试值为 3677
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:98 个元素
---------97----------
测试值为 538
已经有70个比我大 不用比我就是前30小 yes
总共遍历了列表里的:72 个元素
---------98----------
测试值为 5585
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:56 个元素
---------99----------
测试值为 6713
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:44 个元素
---------100----------
测试值为 9837
已经有30个比我小 我不是前30小 no
总共遍历了列表里的:30 个元素

Answer 6

直接遍历一遍即可，如果发现有30个数大于它，就可以判断，所以最快判断30次，最差判断99次即可

Answer 7

what im thinking the complexity is log(n) given the algo is a slight modification to quick sort.

select an element r randomly from the array.
partition the array into 2 halves, left & right such that left have elements less than or equal to the selected element r and right has elements of higher value than r.
now count the number of elements in left.
if n = size(left) return element r.
else if n < size (left) repeat the process on left array and ignore the right array elements.
6 else if n > size (left), ignore left array & randomly selected element r and repeat the process on right array to fine the element of order [n - size(left) - 1]. (-1 for randomly selected element).

写产品你需要使用stl::nth_element(), 这个stl方法实际上实现了以上算法。

兄弟在准备面试么，这个微软和google最爱的题目之一。