有鑑於雖然為本科系(資管)，但是實際上在學校時期學習資料結構與演算法時，雖然那個時候都算有印象，但是都畢業這麼久了，除了偶爾看到針對 特定演算法討論，但其實更常使用的其語言函式庫提供的排序/查找，甚至Linq語法讓我們不用看到那些也可以寫出對應的程式。

最近有機會做到一些 LeetCode，汗顏只能第一直覺使用暴力法來解決問題。因此為了隨時能補足觀念問題，包含預備未來可能會遇到Dynamic Programming的演算法大魔王，因此從Udemy大特價時，快速入手了以下課程。課程連結: https://www.udemy.com/course/algorithm-data-structure/ (老師的數學觀念好，好羡慕)

從書本時代過來的我，也開始意識到其實數位課程若在合理價格的情況下，其實可以合適的當作數位書籍看待，甚至可以在anytime，anywhere(包含陪小孩去上游泳課)的時候隨時拿出來找章節來聽 ，著實方便。以下就是我重溫前幾章節 的時候，覺得不錯的技巧，事實上真實案例中 ，都會用到。不過遇到解題的時限跟題目內容理解分析過程。其實很容易 無腦使用暴力法。但下面的技巧其實就是幫助未來就算是使用O(N^2)以上的複雜度。也可以再想看看能否改善為O(N)甚至 O(logN)的方向。也作為一個小筆記吧。順勢把一些重點就重溫過一下。

Counter 技巧

使用hashtable做key/value計算次數

範例題:

Coding Practice:Intersection Problem

若寫成O(n^2)複雜度就會如下 (其關鍵是O(M*N))，有巢狀迴圈

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
	   var result = Intersection(new []{1, 3, 5, 7, 9}, new[]{2, 3, 5, 8, 10});
	   foreach(var item in result)
	   {
	       Console.WriteLine(item);
	   }	
	}
	
	public static int[] Intersection(int[] arr1, int[] arr2)
	{
	   var result = new List<int>();
	   for (int i = 0; i < arr1.Length; i++)
	   {
	      for (int j = 0; j < arr2.Length; j++)
	      {
		if (arr1[i] == arr2[j])
		   result.Add(arr1[i]);
		}
	      }
		
	      return result.ToArray();
	   }
}

用Counter改寫

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var result = Intersection(new []{1, 3, 5, 7, 9}, new[]{2, 3, 5, 8, 10});
		foreach(var item in result)
		{
			Console.WriteLine(item);
		}
		
	}
	
	public static int[] Intersection(int[] arr1, int[] arr2)
	{
		var result = new List<int>();
		var counter = new Dictionary<int, int>();
		for (int i = 0; i < arr1.Length; i++)
		{
			if (counter.ContainsKey(arr1[i]))
			{
			   counter[arr1[i]]++;
			}
			else
			{
			   counter.Add(arr1[i], 1);
			}
		}
		
		for (int i = 0; i < arr2.Length; i++)
		{
			if (counter.ContainsKey(arr2[i]))
			{
			   counter[arr2[i]]++;
			}
			else
			{
			   counter.Add(arr2[i], 1);
			}
		}
		
		foreach(var kv in counter)
		{
			if (kv.Value > 1)
			{
			   result.Add(kv.Key);
			}
		}
		
		return result.ToArray();
	}
	
}

透過Counter計數器變成分別走訪3個迴圈，其BigO應為O(m+n+m+n) = O(2(m+n)) = O(N)(常數可忽略)

課程中 再舉了一個可以用Counter解決的問題如下 :

Coding Practice:Frequency Problem

sameFrequency(“abbc”, “aabc”) false;
sameFrequency(“abba”, “abab”) true;
sameFrequency(“aasdebasdf”, “adfeebed”) false;

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		Console.WriteLine(sameFrequency("abbc", "aabc")); // false;
		Console.WriteLine(sameFrequency("abba", "abab")); //true;
		Console.WriteLine(sameFrequency("aasdebasdf", "adfeebed"));// false;
	}
	
	public static bool sameFrequency(string string1, string string2)
	{
		var arr1 = string1.ToCharArray();
		var arr2 = string2.ToCharArray();
	
		if (arr1.Length != arr2.Length)
			return false;
		
		
		var counter1 = new Dictionary<char, int>();
		var counter2 = new Dictionary<char, int>();
		
		for(int i = 0; i < arr1.Length;i++)
		{
			if (counter1.ContainsKey(arr1[i]))
			{
				counter1[arr1[i]]++;
			}
			else
			{
				counter1.Add(arr1[i], 1);
			}	
		}
		
		for(int i = 0; i < arr2.Length;i++)
		{
			if (counter2.ContainsKey(arr2[i]))
			{
				counter2[arr2[i]]++;
			}
			else
			{
				counter2.Add(arr2[i], 1);
			}	
		}
		
		foreach(var kv in counter1)
		{
			if (!counter2.ContainsKey(kv.Key))
			{
				return false;
			}
			
			if (counter2[kv.Key] != kv.Value)
			{
				return false;
			}
		}
		
		return true;
	}
	
}
在上述的程式中，可以看到篇幅不小，而且3個獨立迴圈。但在演算法時間複雜度的概念中
O(N+M+k)永遠優於O(N*M*K)，當然你可以說某一個值很小，但我們通常是假設平均的概念，所以很小情境反而應該視為特例。

Pointer技巧(TwoPointer)

透過多重指針走訪所有節點

Coding Practice: Average Pair
given sorted array , find 2 integer that average is given avg value
averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);

一樣若用暴力法，做O(n^2)的解法如下:

using System;
using System.Collections;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var resultArray = averagePair(new int[]{-11, 0, 1, 2, 3, 9, 14, 17, 21}, 1.5);
		foreach(var itemArray in resultArray)
		{
			Console.WriteLine("--------------");
			foreach(var item in itemArray)
			{
				Console.WriteLine(item);
			}
		}
	}
	
	public static List<int[]> averagePair(int[] array, double avg)
	{
		var result = new List<int[]>();
		var count = 0;
		for (int i = 0; i < array.Length - 1; i++)
		{
			for (int j = i+1; j < array.Length; j++)
			{
				if ((double)(array[i] + array[j]) / 2 == avg)
				{
					result.Add(new[]{array[i], array[j]});
				}
				count++;
			}
		}
		
		Console.WriteLine("total check step:" + count);
		return result;
	}	
}

結果: total check step:36 (C9取2 = 9*8/2 = 36)
————–
-11
14
————–
0
3
————–
1
2

若改用Pointer的技巧可以指定一個left pointer跟right pointer(也常稱two pointer)

using System;
using System.Collections;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var resultArray = averagePair(new int[]{-11, 0, 1, 2, 3, 9, 14, 17, 21}, 1.5);
		foreach(var itemArray in resultArray)
		{
			Console.WriteLine("--------------");
			foreach(var item in itemArray)
			{
				Console.WriteLine(item);
			}
		}
	}
	
	public static List<int[]> averagePair(int[] array, double avg)
	{
		var result = new List<int[]>();
		var count = 0;
		
		var left = 0;
		var right = array.Length-1;
		
		
		while(left < right)
		{
			var temp = (double)(array[left] + array[right]) / 2;
			
			if (temp > avg)
			{
				right--;
			}
			if (temp < avg)
			{
				left++;
			}
			if (temp == avg)
			{
				result.Add(new[]{array[left], array[right]});	
				right--;
				left++;
			}
			count++;
		}
		
		Console.WriteLine("total check step:" + count);
		return result;
	}	
}

Result:

total check step:6
————–
-11
14
————–
0
3
————–
1
2

同樣的結果，可以在9步內(6步)找到一樣結果

複雜度也從巢狀迴圈走訪改成了每個節點最多走訪一次甚至因為two pointer，可以少了3次比對。

因為結果有3個符合，所以一次性left跟right同時會往內縮小範圍。

Sliding Window技巧

透過window size走訪所有的節點。每一次以給定的size橫向 移前一格索引。

Coding Practice:maxSum/minSum

given integer array , find consecutive number of given n value ‘s max and min value

maxSum([2,7,3, 0,6,1,-5,-12,-11], 3)

//minSum([2,7,3, 0,6,1,-5,-12,-11], 3)

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var result = maxSum(new int[]{2,7,3, 0,6,1,-5,-12,-11}, 3);
		Console.WriteLine(result);	
	}
	
	public static int? maxSum(int[] array, int size)
	{
		if (array.Length < size)
			return null;
		
		var count = 0;
		var max = int.MinValue;
		for (int i = 0 ; i < array.Length - size; i++)
		{
			var temp = 0;
			for (int j = i; j < i + size; j++) //
			{
				temp += array[j];
				count++;
			}
			
			if (temp > max)
				max = temp;
		}
		Console.WriteLine(count);
		return max;
	}
}

上面程式的走法是 O(N*M)複雜度。(加總的迴圈的操作也是要算複雜度，也端看size的大小)

Count: 18
maxSum: 12

改善Sliding Window的寫法:

using System;
using System.Collections.Generic;
					
public class Program
{
	public static void Main()
	{
		var result = maxSum(new int[]{2,7,3, 0,6,1,-5,-12,-11}, 3);
		Console.WriteLine(result);	
	}
	
	public static int? maxSum(int[] array, int size)
	{
		if (array.Length < size)
			return null;
		
		var count = 0;
		var max = 0;
		
		//first window
		for (int i = 0 ; i < size; i++)
		{
			max += array[i];
			count++;
		}
				
		for (int j = size ; j < array.Length; j++)
		{
			var temp = max + array[j] - array[j-size];
			if (temp > max)
				max = temp;
			
			count++;
		}
		
		Console.WriteLine(count);
		
		return max;
	}	
}

Count: 9
maxSum: 12
同樣的例子變成了9次，整整省了1/2的複雜度，且變成了O(N)的複雜度(稱為線性時間)，當然那個迴圈加總還是一個關鍵。因為size不可知，所以用 迴圈動態處理，但是用sliding window的話，就每次滑動一格，所以是在可預期的步數下去做操作。最多2步。因此這也是一個滿有名的演算法，可以幫助我們在一個循序集合中，找到滿足特定條件的目標值或目標集合。

以上3個 小技巧重點重溫~下集待續~~

https://www.hackerrank.com/challenges/one-week-preparation-kit-new-year-chaos/problem?h_l=interview&isFullScreen=true&playlist_slugs%5B%5D%5B%5D=preparation-kits&playlist_slugs%5B%5D%5B%5D=one-week-preparation-kit&playlist_slugs%5B%5D%5B%5D=one-week-day-four

測試案例

    public static void minimumBribes(List<int> q)
    {
        var total =0;
        for(int i = q.Count-1; i > 0; i--)
        {
            if (q[i-1] == i+1)
            {
                q[i-1] = q[i];
                total++;
            }
            else if (i>=2 && q[i-2] == i+1)
            {
                q[i-2] = q[i-1];
                q[i-1] = q[i];
                total+=2;
            }
            else if (q[i] != i+1){
                Console.WriteLine("Too chaotic");
                return ;
            }
        }   
        Console.WriteLine(total);
    }

這題老實說，很難看的懂...就算是看答案也一樣

基本上就是帶入程式研究一輪變化吧

首先 傳入的參數 2 1 5 3 4
一開始返向逐一抓值出來，因為假設是由排在後面的人往前做賄絡
順序就是4, 3, 2, 1, 0(index) 
按index就是 
index: 4, 3, 2, 1, 0
value: 4, 3, 5, 1, 2 這個順序來看 

首先index=4時
先
判斷 q[3]若前一個等於5(i+1)，代表可以經過換過了一次達成
但這個時候，並不是，這時的q[3]是3，判斷不符
value: 4, 3, 5, 1, 2 

否則 再判斷q[2](i-2，表示前2個)是不是5，
結果符合:
value: 4, 3, 5, 1, 2 
代表可以經由換2次做到5變成index=3的位置
所以試著做
第3個位置換回第4個位置 
index: 4, 3, 2, 1, 0
value: 4, 5, 3, 1, 2  
而第4個位置=第5個位置。
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
然後步驟+2;

再來index=3時
一樣做上述判斷
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
先看前一個q[2]等於4，結果不是
然後看q[1]前2個是否等於4，結果也不是
最後看，第3個是不是等於4，也不是。
這一輪結束

再來index=2時 
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
若前一個q[1]是否等於3，結果不是
然後看 q[0]是否等於3，結果也不是
最後看，第2個是不是等於3，也不是
這一輪結束

再來index = 1時
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 1, 2 
若前一個q[0]是否等於2，結果符合
這時將 q[i-1] = q[i]
最後組合為
index: 4, 3, 2, 1, 0
value: 5, 4, 3, 2, 1 
然後步驟++，此時步驟=3

結束>0的迴圈
印出 total=3;


這個迴圈裡的條件判斷就是假設從最後面一排往前看
若是可以透過假設一步換掉的話，就把他還原
假如可以透過 二步換掉的話，就也把他還原。
否則的話，若比較的值沒有出現在前1、2個位置也沒出現在原位的話，代表 最高可能要超過2步才能達成。所以就印出too chaotic

概念走訪如上...實際寫的話..可能要多記憶一下這個脈絡...XD



Reference :
https://www.youtube.com/watch?v=eFIYc7E4cmQ

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

看起來很單純的題目
我第一階段的暴力解 是取餘數* 10的(長度-1)次方，每次長度都--;
結果在 大數處理的時候溢位問題很多

寫法最終如下
namespace TestProject1.Reverse_Integer;

public class ReverseInteger
{
    public int Reverse(int x)
    {
        var s = 0;
        while (x != 0)
        {
            var r = x % 10;

            var temp = s * 10 + r;

            if ((temp - r) / 10 != s) //避免溢位問題
                return 0;

            s = temp;
            x /= 10;
        }

        return s;
    }
}

using FluentAssertions;
using NUnit.Framework;
using TestProject1.Reverse_Integer;

public class ReverseIntegerTest
{
    [SetUp]
    public void Setup()
    {
    }

    [Test]
    public void Test001()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(123);
        result.Should().Be(321);
    }
    
    [Test]
    public void Test002()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(-123);
        result.Should().Be(-321);
    }
    
    [Test]
    public void Test003()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(120);
        result.Should().Be(21);
    }  
    
    [Test]
    public void Test004()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(1534236469);
        result.Should().Be(0);
    }
    
    [Test]
    public void Test005()
    {
        ReverseInteger ts = new ReverseInteger();
        var result = ts.Reverse(32768);
        result.Should().Be(86723);
    }    
    
}

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

using System;
using System.Collections.Generic;

public class ThreeSumSolution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        if (nums.Length < 3) return new List<IList<int>>();
        Array.Sort(nums);

        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < nums.Length - 2; i++)
        {
            var j = i + 1; //left
            var k = nums.Length - 1; //right
            //排序後，每次 第一位取出來的時候，若後面的值跟前面一樣，代表 前面就循環過了，就不再比較一次 ，直接跳下一個
            //ex [1, 1, 2, 3, 4]
            // 若i=1，值是1，但i=0已經比較過 值是1的，所以SKIP
            if (i > 0 && nums[i] == nums[i - 1]) continue; 
            
            //雙指針
            while (j < k)
            {
                //ex [1, 1, 2, 3, 4]
                // i = 0, 這時j是1，k是3，兩兩 與第i項加總
                
                var sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) //若剛好=0，是我們要的組合
                {
                    result.Add(new List<int>() {nums[i], nums[j], nums[k]});
                    while (j < k && nums[j] == nums[j + 1]) j++; //因為排過序，判斷 往右 是 不是一樣的數字，若是一樣的數字就 再++往右跳過
                    while (j < k && nums[k] == nums[k - 1]) k--; //因為排過序，判斷 往左 是 不是一樣的數字，若是一樣的數字就 再--往左跳過

                    //上面的小while只是累加到重覆的那一個位置 下面還是要再各別往內逼近
                    j++;
                    k--;
                }
                else if (sum < 0)
                {
                    //因為排序過，因此若和小於0，代表 需要從中間數往右找更大的數字看看，所以左指針++
                    j++;
                }
                else
                {
                    //因為排序過，因此若和大於0，代表 需要從最右的大數往左找更小的數字看看，所以右指針--
                    k--;
                }
            }
        }

        return result;
    }
}

using FluentAssertions;
using NUnit.Framework;

public class ThreeSumTests
{
    [SetUp]
    public void Setup()
    {
    }

    [Test]
    public void Test001()
    {
        ThreeSumSolution ts = new ThreeSumSolution();
        var result = ts.ThreeSum(new[] {-1, 0, 1, 2, -1, -4});
        result.Count.Should().Be(2);
    }
}

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

• 1 <= task.length <= 104
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100].

using System;
using System.Collections.Generic;
using System.Linq;

public class TaskScheduler
{
    public class task
    {
        public char name { get; set; }
        public int count { get; set; }
    }

    public int LeastInterval(char[] tasks, int n)
    {
        if (0 == n) return tasks.Length;

        Dictionary<char, int> counter = new Dictionary<char, int>();
        foreach (var task in tasks)
        {
            if (counter.ContainsKey(task))
            {
                counter[task]++;
            }
            else
            {
                counter.Add(task, 1);
            }
        }

        int chCount = 0, maxCount = 0, step = 0;
        foreach (var item in counter.Values)
        {
            if (item > maxCount)
            {
                chCount = 1;
                maxCount = item;
            }
            else if (item == maxCount)
            {
                chCount++;
            }
        }
       
        if (step >= tasks.Length) return step;
        return tasks.Length;
    }
}

using FluentAssertions;
using NUnit.Framework;

namespace TestProject1.TaskScheduler;

public class SolutionTests
{
    [SetUp]
    public void Setup()
    {
    }

    global::TaskScheduler _scheduler = new global::TaskScheduler();

    [Test]
    public void Test001()
    {
        var result = _scheduler.LeastInterval(new char[] {'A', 'A', 'A', 'B', 'B', 'B'}, 2);
        result.Should().Be(8);
    }    
    
    [Test]
    public void Test002()
    {
        var result = _scheduler.LeastInterval(new char[] {'A','A','A','B','B','B'}, 0);
        result.Should().Be(6);
    }
    
    [Test]
    public void Test003()
    {
        var result = _scheduler.LeastInterval(new char[] {'A','A','A','A','A','A','B','C','D','E','F','G'}, 2);
        result.Should().Be(16);
    }
}

step = (maxCount – 1) * (n + 1) + chCount;
公式這邊真的看無 ，看起來是找到最大重覆的task的次數後
實際推論上就是

例如new char[] {‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’}, 2
那麼就是 A有3，B有3，n=2 那maxCount = 3, chCount = 2 (因為 > 0的時候 chcount就 =1，若有重覆次數的就再 +=1 )
所以step = (3-1)*(2+1) + 2 = 8

再假如new char[] {‘A’,’A’,’A’,’A’,’A’,’A’,’B’,’C’,’D’,’E’,’F’,’G’}, 2

那麼A有6，B~G各有1
那麼maxCount = 6
公式變成( 6-1) * (2+1)+1=16

照公式的概念就是，最多次數的task，肯定要被n次的限制卡住。若每一次的循環都要跑一次 A+?+?，代表 中間不論是塞次數少的的Task，若分配完了也是要塞 Idle Task。
那麼就代表至少要跑 6個就有5個區間，每個區間都至少要含自已是3個步驟。所以就是15次
那為啥chCount = 1。因為5個區間會少算最後一個出頭的Task。因為B~G總共也在 5次 ，剛好分配到5個區間中的間隔中，代表 塞完間隔後，因為次數不足，還要塞idle，才能再讓 次數最多的跑。

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

public class Solution {
	public int[] TwoSum(int[] nums, int target) {
        Hashtable hash = new Hashtable();
        for (int i = 0; i < nums.Length; i++)
        {
            var complement = target - nums[i];
            if (hash.ContainsKey(complement))
            {
                return new int[]{(int)hash[complement], i};
            }
            else
            {
                if (hash.ContainsKey(nums[i]) == false)
                    hash.Add(nums[i], i);
            }
        }
        
        return null;
    }
}

多年前練習過的題目，暴力解是兩個迴圈去倆倆比對(O(N²)，此題更優的解法是利用HashTable去建立快取

每比對到跟目標的差，都先記到hashtable中，直到遍歷了每一個元素一次就好，若剛好match到，就代表找到結果了！這樣的話就至少是O(N)的複雜度了。

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1

Constraints:

• n == citations.length
• 1 <= n <= 5000
• 0 <= citations[i] <= 1000

Version 1

public class Solution {
        public int HIndex(int[] citations)
    {
       var length = citations.Length;

        var index = 0;
        for (int i = 1; i <= length ; i++)
        {
            var count = citations.Count(a=>a>=i);
            if (count >= i && i > index)
                index = i;
        }

        return index;
    }

}

//testing Code
    H_Index _indexer = new H_Index();

    [Test]
    public void Test001()
    {
        _indexer.HIndex(new int []{3, 0, 6, 1, 5}).Should().Be(3);
    }
    
    [Test]
    public void Test002()
    {
        _indexer.HIndex(new int []{1, 3, 1}).Should().Be(1);
    }

直覺的思路在一開始我確實沒有看理解，所以一直沒看準一個原則就是h值必須同時要在陣列中找到至少 >= h值有h個項目。這兩個必須相等，一開始我還以為是要找出符合hindex的陣列位置。

送出後一看不得了，笑死，這複雜度是O(N²)，而且以提交結果才beat 5.74%，代表一定要再想辦法優化了

第二版本

其實簡化計算規則，就是先排序由大到小，然後比對若>指數，就指數累加(=不累加)

var sorted = citations.OrderByDescending(a=>a).ToArray();

var h = 0;
foreach (var value in sorted)
{
    if (value > h)
        h++;
}

return h;

這個版本是Linq 對int[]的排序是O(n log n)

看看其他人的版本改寫如下(beat 95%)

C#陣列預設排序為 快速排序，也是O(nlogn)，再走訪一次n個迴圈是O(n)，表示方式為 O(n log n + n )直接呈現O(n log n)，因為由大到小，所以一旦比對不符合就可以break掉