[演算法][SQL]演算法挑戰系列(3)-Nth Highest Salary

sql ms sql

神Q超人 2018-05-18 20:52:25 ‧ 6126 瀏覽

分享至

哈囉！我又來了，每週一篇文章應該是對我而言最舒服的頻率了，好啦！那是題外話XD

話說上一個禮拜的SQL挑戰出乎意料的出現很多高手，也在這裡感謝大家願意分享自己的解法，我也很開心可以在自己的文章下能有這樣子的程式小交流，那今天的主題就繼續來玩SQL吧！

題目名稱：Nth Highest Salary
難易度：中
題目內容：將參數n傳入FunctiongetNthHighestSalary(n)，並回傳Employee資料表中領第n高的薪水金額。
例如：
1.Employee資料表：

Id	Salary
1	100
2	200
3	300
`getNthHighestSalary(2)`，將n以2帶入函式，讓函式回傳`Employee`資料表中第2高的薪水金額，所以答案是200。

2.Employee資料表：

Id	Salary
1	100
2	100
`getNthHighestSalary(2)`，將n以2帶入函式，讓函式回傳`Employee`資料表中，第2高的薪水金額，但是因為表中只有100一個薪額，沒有所謂的第二高，所以得回傳null。

好的，那接下來就開始吧！

/*建立一個能夠傳入參數 @N 的Function*/
CREATE FUNCTION getNthHighestSalary(@N INT) RETURNS INT AS
/*T-SQL的範圍開始*/
BEGIN
    /*直接回傳*/
    RETURN (
        /*用DISTINCT過濾掉相同金額的薪水*/
        SELECT DISTINCT Salary
        FROM Employee
        /*將金額由大到小排列*/
        ORDER BY Salary DESC
        /*用分頁語法取出略過 @N 筆資料後的第1筆資料
        如果 @N 為1就要帶出第一高，所以略過0(@N-1)筆資料
        如果 @N 為2就要帶出第二高，所以略過1(@N-1)筆資料*/
        OFFSET (@N-1) ROWS FETCH NEXT 1 ROWS ONLY
    );
/*T-SQL的範圍結束*/
END

上面是我的個人解法XD，另外我在問題討論區中有看到一個覺得還滿特別的解法，和大家分享該網友解法：

/*建立一個能夠傳入參數 @N 的Function*/
CREATE FUNCTION getNthHighestSalary(@N INT) RETURNS INT AS
/*T-SQL的範圍開始*/
BEGIN
    RETURN (
        /*(3)最後再查出不重複的薪水，也就是第幾名*/
        SELECT DISTINCT salary 
        FROM   employee e1 
        /*(2)拿到排名後就可以直接和 @N 做比較，看哪一個排名符合條件*/
        WHERE  @N = 
            /*(1)精華就在這個子查詢了，他JOIN了外面層資料表的薪水，
            並比較內層大於等於該薪水的數量有幾個，
            如果外面的薪水最高是300，那JOIN到內層資料表大於等於300的個數就一個，
            如果外面的薪水第二高是200，那JOIN到內層資料表大於等於200的個數就兩個，
            所以經過子查詢處理，其實就可以帶出各金額的排名*/
            (SELECT COUNT(DISTINCT salary) 
            FROM   employee e2 
            WHERE  e1.salary <= e2.salary) 
    );
/*T-SQL的範圍結束*/
END

ㄛ，解讀程式碼真的就和翻譯原文書一樣困難，還請大家多多包涵，我盡量使用(1)(2)(3)的順序講解，如果有哪邊搞錯了還請各位大大留言告訴我。

這次的題目就是屬於T-SQL的應用了，但是因為不是很困難，所以還是可以直接在RETURN內寫SQL語法來處理掉這一題，不過以後如果真的碰到T-SQL的題目就要開始爬文研究了，，另外提醒一下，上方的註解都是我在編輯文章的時候才打上去的，如果要直接貼到該網站去執行，要記得先把註解都拿掉，因為我提交執行只要有註解都會出錯。

那歡迎大家如果有什麼文章內問題，或是如果發現有什麼也是很好用的演算法網站、題目，都可以在下方留言告知我，謝謝大家！

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

3 則留言

暐翰

iT邦大師 1 級 ‧ 2018-05-18 23:19:09

喜歡你的這系列，我都有在Follow

以下是我嘗試的直覺寫法
邏輯寫在註解裡面
因為是直覺寫法可能會有問題
假如有問題麻煩跟我說一下

----建立測試資料----
CREATE TABLE Employee
    ([Id] int, [Salary] int)
;
    
INSERT INTO Employee
    ([Id], [Salary])
VALUES
    (1, 100),
    (2, 200),
    (3, 300),
    (4, 100),
    (5, 100),
    (6, 20),
    (7, 50)
;

----修改版---- 
CREATE FUNCTION dbo.Getnthhighestsalary (@N int)
RETURNS int
AS
BEGIN
  RETURN (SELECT
    salary
  FROM (SELECT 
    --【第三步】使用row_number來取得薪水排名，讓@N可以當條件篩選資料用 
    ROW_NUMBER() OVER (ORDER BY salary DESC) rnk
    --【第二步】挑出不重複的薪水
    ,salary
  FROM employee
  --【第一步】需要使用Group by 把重複值篩選掉
  GROUP BY salary) T
  WHERE rnk = @N)
END;

--驗證 
SELECT
  dbo.Getnthhighestsalary(3) id --因為有相同資料所以回傳null 
UNION ALL
SELECT
  dbo.Getnthhighestsalary(1) id --排名第一300

結果

效率

主要效率都花在"排序"跟"全表搜尋"
效率比78:22

SQL Fiddle

回應 6
檢舉

看更多先前的回應...收起先前的回應...

神Q超人 iT邦研究生 5 級 ‧ 2018-05-19 20:14:50 檢舉

我也常常從大大在回答區的回答學到不少東西，尤其是每一次的問答都寫得很清楚，更厲害的是連提供方法的效能都會測試過，讓小弟非常佩服
另外我覺得大大用row_number()的方法很棒，我還沒有想過XD，話說其實題目不是重複的顯示null，而是如果沒有所謂的第幾高，才顯示null，例如大大的範例資料表裡面有300，200，100，50，20，五種新額，如果我在函式中的@N傳入6才顯示null，如果傳3還是回傳100沒錯，可能是我的題目解釋不太清楚

暐翰 iT邦大師 1 級 ‧ 2018-05-19 20:36:24 檢舉

我修改了!
這是我的問題
最近看文章都用掃描式的讀法,會漏東漏西 (檢討ing)

神Q超人 iT邦研究生 5 級 ‧ 2018-05-19 23:51:25 檢舉

哈哈哈，不會啦！
感謝你願意分享做法，歡迎常來ㄚ

純真的人 iT邦大師 1 級 ‧ 2018-05-20 12:10:55 檢舉

哈~我想的方式跟暐翰一樣~沒別的方式想法了~

神Q超人 iT邦研究生 5 級 ‧ 2018-05-20 13:36:17 檢舉

回純真的人
下面的fysh711426有用另外一種DENSE_RANK()也很好用~~

純真的人 iT邦大師 1 級 ‧ 2018-05-20 15:32:37 檢舉

喔喔~沒想到呢~~

登入發表回應

小魚

iT邦大師 1 級 ‧ 2018-05-19 15:37:26

我想說，這不是直接用SQL就可以了嗎?
不過我也是太少接觸預存程序了，
找個空檔來練習一下吧...

補充：
我的解法跟暐翰類似，不過我把重複的當成有效的

CREATE FUNCTION [dbo].[getNthHighestSalary]
(
 @N INT
)
RETURNS INT AS
BEGIN
	RETURN (
	SELECT Salary FROM (
		SELECT Salary, ROW_NUMBER() OVER (ORDER BY Salary DESC) AS row
		FROM Employee
		GROUP BY Salary
	) AS a 
	WHERE row = @N
	);
END;

回應 3
檢舉

暐翰 iT邦大師 1 級 ‧ 2018-05-19 17:07:18 檢舉

不是直接用SQL就可以了嗎?

這跟C#方法類似
把商業、特殊邏輯包在一個function去call帶參數就可以得到要的結果
不用再重新寫一個SQL

PS.
邏輯複雜的時候，除非特殊情況
我喜歡寫在C#方法而非DB的function
享受強型別維護好處

以上個人看法 :-)

小魚 iT邦大師 1 級 ‧ 2018-05-19 18:30:19 檢舉

暐翰
我也都是用C#的Function，
很少在用DB的Function，
不過有些時候用DB的方法效率會比較高，
所以這個也是要學習的。

神Q超人 iT邦研究生 5 級 ‧ 2018-05-19 20:20:35 檢舉

暐翰、小魚，兩位大大好，其實我也都寫在C#比較多，所以我SQL其實算滿弱的，目標就只放在把資料撈出來而以，不太會比較效率，所以就像小魚大大說的，如果有學習的機會這也是可以去熟悉的

登入發表回應

小碼農米爾

iT邦高手 1 級 ‧ 2018-05-20 10:50:56

我用 DENSE_RANK()，第一次寫 FUNCTION

ALTER FUNCTION getNthHighestSalary(@N INT)
RETURNS INT
AS
BEGIN
	
	RETURN (
		SELECT DISTINCT Salary
		FROM (
			SELECT *,
			       DENSE_RANK() OVER (ORDER BY Salary DESC) AS SRank
			FROM Employee 
		) AS A
		WHERE A.SRank=@N
	)

END