尋找亂序數組中特殊數

其實我前幾天發過一樣的題，但好像我表達題目不夠清楚沒得到答案，我想了好幾天還是沒想到，想再來問問看有沒有人會。這題有點像数组中的第K个最大元素的變異題：給定一個亂序數組 Ａ，輸出一個特定數字x，其中數字'x' 為數列中的第x大，若無此數字則輸出 -1
例子：-9,8,1,-1,2 則輸出 2 因為2 “恰好”是此數列中第二大的數
因為一共有n個數，得確認 第 1 到 第n-1 大的數 是不是剛好等於數字本身
我知道要用QuickSelect  但是細節上每次遞迴呼叫要改變的Index我一直沒搞懂如何用Select寫出Ｏ（Ｎ）的解法><

感激不盡！！！

不需要啥qucik select.
假设有n个元素。你建立一个长度为n+1的数组count。扫一遍每个元素x，就更新count[x]+=1，特别的对于x>n, 你更新count[n+1]+=1
然后你对count从高到底走一遍 i。你就可以知道大于等于i的元素有几个。如果恰好有i个，那么i就是你要的答案。

有两点看法：
1. 非正数的话应该不对，除非你说-5大的就是第5小的。。
2. 考虑正数。例如 [8,2,0,-1,-9,3,-4,6,-2]，排好序之后是 [-9,-4,-2,-1,0, 2, 3, 6, 8]。假如我们第一次用quickSelect选的pivot是8，而发现8是1st大的，但是8>1，这个时候我们就知道应该找比8要小的位置；第二次我们如果碰巧选了pivot是2，发现2是第4th大的，而2<4， 所以我们需要找比2大的。这样夹逼之后看是否有答案，有的话输出，没有的话返回-1.

最后请问：这是谁家的什么面试题？

-9,8,1,-1,2 則輸出 2 因為2 “恰好”是此數列中第二大的數

2是第三大的数字诶 是我理解错了还是你写错了 》。《

匿名的 发表于 2021-3-2 02:31
-9,8,1,-1,2 則輸出 2 因為2 “恰好”是此數列中第二大的數

2是第三大的数字诶 是我理解错了还是你写错 ...

咦 第一大是8 第二大是 2, 沒錯吧...

AmberLNLF 发表于 2021-3-2 02:45
咦 第一大是8 第二大是 2, 沒錯吧...

我理解错了 抱歉！

感觉QuickSelect不能做

bmiyc2 发表于 2021-3-2 05:00
-9

我猜根据楼主的意思，具体找第几大是data dependent的。返回的数n是数组的第n大。