iT邦幫忙

5

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

哈囉!我又來了,每週一篇文章應該是對我而言最舒服的頻率了,好啦!那是題外話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

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

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

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


4
暐翰
iT邦高手 1 級 ‧ 2018-05-18 23:19:09

喜歡你的這系列,我都有在Follow
/images/emoticon/emoticon12.gif

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

----建立測試資料----
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

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

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

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

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

哈哈哈,不會啦!
感謝你願意分享做法,歡迎常來ㄚ/images/emoticon/emoticon37.gif

純真的人 iT邦研究生 3 級‧ 2018-05-20 12:10:55 檢舉

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

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

純真的人 iT邦研究生 3 級‧ 2018-05-20 15:32:37 檢舉

喔喔~沒想到呢~~

1
小魚
iT邦研究生 2 級 ‧ 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;
暐翰 iT邦高手 1 級‧ 2018-05-19 17:07:18 檢舉

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

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

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


以上個人看法 :-)

小魚 iT邦研究生 2 級‧ 2018-05-19 18:30:19 檢舉

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

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

2
fysh711426
iT邦新手 2 級 ‧ 2018-05-20 10:50:56

我用 DENSE_RANK(),第一次寫 FUNCTION
/images/emoticon/emoticon16.gif

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
看更多先前的回應...收起先前的回應...
小魚 iT邦研究生 2 級‧ 2018-05-20 11:16:28 檢舉

我也是第一次寫,請多指教。
不過原來有這麼好用的函數,
我也是要多學習...

DENSE_RANK()真的是第一次看到!
原來SQL中有那麼多排名的函數,要找時間來整理一下了/images/emoticon/emoticon13.gif

暐翰 iT邦高手 1 級‧ 2018-05-20 13:43:11 檢舉

/images/emoticon/emoticon12.gif 這樣就不用group by了

小魚 請多指教((握手
神Q超人 哈哈哈,排名函數很好用,話說大家都對SQL很有興趣呢!!
暐翰 但還是要 DISTINCT,有在想如果重複的資料多好像用 TOP 1 會比較快。

小魚 iT邦研究生 2 級‧ 2018-05-20 16:02:24 檢舉

TOP 1也可以考慮...

對啊!我都拋棄最愛的JavaScript兩個禮拜了/images/emoticon/emoticon25.gif

我要留言

立即登入留言