C#中提供的多种集合类以及适用场景

在 C# 中，有多种集合类可供使用，它们分别适用于不同的场景,部分代码示例提供了LeetCode相关的代码应用。

1. 数组（Array）

特点
- 固定大小：在创建数组时需要指定其长度，之后无法动态改变。
- 连续存储：数组元素在内存中是连续存储的，因此可以通过索引快速访问元素，访问时间复杂度为 O(1)。
- 类型固定：数组中的所有元素必须是相同类型。
示例代码

  int[] numbers = new int[5] { 1, 5, 2, 3, 4 };
  numbers[0] = 1;//update
  int firstNumber = numbers[0];
  int lastNumber = numbers[numbers.Length - 1];
  Array.Sort(numbers);//排序

LeetCode: 106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

public TreeNode BuildTree(int[] inorder, int[] postorder)
{
    if (inorder.Length == 0 || postorder.Length == null) return null;
    int rootValue = postorder.Last();
    TreeNode root = new TreeNode(rootValue);
    int delimiterIndex = Array.IndexOf(inorder, rootValue);
    root.left = BuildTree(inorder.Take(delimiterIndex).ToArray(), postorder.Take(delimiterIndex).ToArray());
    root.right = BuildTree(inorder.Skip(delimiterIndex + 1).ToArray(), postorder.Skip(delimiterIndex).Take(inorder.Length - delimiterIndex - 1).ToArray());
    return root;
}

2. 动态数组（List<T>）

特点
- 动态大小：可以根据需要动态添加或删除元素，无需预先指定大小。
- 连续存储：内部使用数组实现，元素在内存中连续存储，支持通过索引快速访问，访问时间复杂度为 O(1)。
- 类型安全：泛型集合，只能存储指定类型的元素。
示例代码

List<int> numberList = new List<int>();
numberList.Add(1);
int firstElement = numberList[0];

3. 链表（LinkedList<T>）

特点
- 动态大小：可以动态添加或删除元素。
- 非连续存储：元素在内存中不连续存储，每个元素包含一个指向前一个元素和后一个元素的引用。
- 插入和删除效率高：在链表的任意位置插入或删除元素的时间复杂度为 O(1)，但随机访问效率低，时间复杂度为O(n) 。
示例代码

            LinkedList<int> numberLinkedList = new LinkedList<int>();
            numberLinkedList.AddLast(1);
            numberLinkedList.AddFirst(2);
            numberLinkedList.AddFirst(3);
            numberLinkedList.Remove(1);
            numberLinkedList.RemoveFirst();
            numberLinkedList.RemoveLast();
            int count=numberLinkedList.Count;
            bool isContains= numberLinkedList.Contains(3);

4. 栈（Stack<T>）

特点
- 后进先出（LIFO）：最后添加的元素最先被移除。
- 动态大小：可以动态添加或删除元素。
- 插入和删除操作快：入栈（Push）和出栈（Pop）操作的时间复杂度为O(1) 。
示例代码

            Stack<int> numberStack = new Stack<int>();
            numberStack.Push(1);

            // Removes and returns the object at the top of the System.Collections.Generic.Stack`1.
            int topElement = numberStack.Pop();

            // Returns the object at the top of the System.Collections.Generic.Stack`1 without removing it.
            topElement = numberStack.Peek(); 
            int count = numberStack.Count;

LeetCode: 144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        var result = new List<int>();

        if (root == null) return result;
        Stack<TreeNode> treeNodes = new Stack<TreeNode>();// 栈是先进后出。 中序遍历是：中--》 左--》右
        treeNodes.Push(root);

        while (treeNodes.Count > 0)
        {
            TreeNode current = treeNodes.Pop();
            result.Add(current.val);// 中

            if (current.right != null)// 右
            {
                treeNodes.Push(current.right);
            }
            
            if (current.left != null)// 左
            {
                treeNodes.Push(current.left);
            }

        }

        return result;
    }
}

5. 队列（Queue<T>）

特点
- 先进先出（FIFO）：最先添加的元素最先被移除。
- 动态大小：可以动态添加或删除元素。
- 插入和删除操作快：入队（Enqueue）和出队（Dequeue）操作的时间复杂度为 O(1)。
示例代码

          Queue<int> numberQueue = new Queue<int>();
          numberQueue.Enqueue(1);

          // Removes and returns the object at the beginning of the System.Collections.Generic.Queue`1.
          int firstElement = numberQueue.Dequeue();

          //Returns the object at the beginning of the System.Collections.Generic.Queue`1 without removing it.
          numberQueue.Peek();
          int count = numberQueue.Count;

LeetCode: 102. 二叉树的层序遍历 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        Queue<TreeNode> queue = new ();
        if (root != null) queue.Enqueue(root);

        while (queue.Count>0)
        {
            var row=new List<int>();
            int count=queue.Count;// 需要事先记录Queue的Count，不能直接依靠Queue本身
            for (int i=0; i < count; i++)
            {
                var currentNode=queue.Dequeue();
                row.Add(currentNode.val);
                if (currentNode.left != null) queue.Enqueue(currentNode.left);
                if (currentNode.right != null) queue.Enqueue(currentNode.right);
            }
            result.Add(row);
        }
        return result;
    }
}

6. 哈希集合（HashSet<T>）

特点
- 唯一元素：集合中不允许有重复的元素。
- 无序：元素在集合中没有特定的顺序。
- 快速查找：插入、删除和查找操作的平均时间复杂度为O(1) 。
示例代码

      HashSet<int> numberHashSet = new HashSet<int>();
      numberHashSet.Add(1);
      bool isAddSuccess = numberHashSet.Add(1);// false

      bool containsOne = numberHashSet.Contains(1);// true

如LeetCode：491. 非递减子序列

public class Solution {
    public IList<IList<int>> FindSubsequences(int[] nums) {
        var result = new List<IList<int>>();
        var path = new List<int>();
        if(nums==null || nums.Length == 0) return result;

        BackTacking(nums,result,path,0);

        return result;
    }

    private void BackTacking(int[] nums,List<IList<int>> result, List<int> path,int startIndex)
    {
        if (path.Count>=2) result.Add(new List<int>(path));
        HashSet<int> used =new HashSet<int>();

        for (int i=startIndex;i<nums.Length;i++)
        {
            if(path.Count>0 && nums[i]<path[path.Count-1]) continue;
            
            bool isUsed=used.Add(nums[i]);// true-添加成功；false-添加失败，证明已经有元素存在了
            if(!isUsed) continue;// 同一层重复使用

            path.Add(nums[i]);
            BackTacking(nums,result,path,i+1);
            path.RemoveAt(path.Count-1);
            
        }
    }
}

7. 字典（Dictionary<TKey, TValue>）

特点
- 键值对存储：通过唯一的键来关联对应的值。
- 快速查找：根据键查找值的平均时间复杂度为 O(1)。
- 键唯一：字典中的键必须是唯一的，但值可以重复。
示例代码

Dictionary<string, int> scores = new Dictionary<string, int>();
scores.Add("Alice", 90);
int aliceScore = scores["Alice"];

LeetCode: 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder)
    {
        if (preorder == null || inorder == null)
        {
            return null;
        }
        /*
         前序遍历   根   左子树 右子树
         中序遍历   左子树 根   右子树
         */

        if (preorder.Length != inorder.Length)
        {
            return null;
        }

        Dictionary<int, int> keyMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++)
        {
            keyMap.Add(inorder[i], i);
        }
        return BuildTree(preorder: preorder, keyMap, preleft: 0, preRight: preorder.Length - 1, inLeft: 0, inRight: inorder.Length - 1);
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="preorder"></param>
    /// <param name="keyMap">用于确定pIndex。Root的Index</param>
    /// <param name="preleft"></param>
    /// <param name="preRight"></param>
    /// <param name="inLeft"></param>
    /// <param name="inRight"></param>
    /// <returns></returns>
    private TreeNode BuildTree(int[] preorder, Dictionary<int, int> keyMap, int preleft, int preRight, int inLeft, int inRight)
    {
        if (preleft > preRight || inLeft > inRight)
        {
            return null;
        }
        int rootValue = preorder[preleft];
        TreeNode treeNode = new TreeNode(rootValue);
        int pIndex = keyMap[rootValue];
        treeNode.left = BuildTree(preorder, keyMap, preleft: preleft + 1, preRight: pIndex + preleft - inLeft, inLeft, inRight: pIndex - 1);//根据PreOrder去取Left node
        treeNode.right = BuildTree(preorder, keyMap, preleft: pIndex + preleft - inLeft + 1, preRight: preRight, inLeft: pIndex + 1, inRight);//根据inOrder去取Right node

        return treeNode;
    }
}

8. 排序集合（SortedSet<T>）

特点
- 唯一元素：集合中不允许有重复的元素。
- 有序：元素会根据元素的自然顺序或指定的比较器进行排序。
- 查找和插入操作：插入、删除和查找操作的时间复杂度为 O(logn)。
示例代码

SortedSet<int> sortedNumbers = new SortedSet<int>();
sortedNumbers.Add(3);
sortedNumbers.Add(1);
// 元素会自动排序，遍历输出为 1, 3
foreach (int number in sortedNumbers)
{
    Console.WriteLine(number);
}

9. 排序字典（SortedDictionary<TKey, TValue>）

特点
- 键值对存储：通过唯一的键来关联对应的值。
- 有序：元素会根据键的自然顺序或指定的比较器进行排序。
- 查找和插入操作：根据键查找值、插入和删除操作的时间复杂度为 O(logn)。
示例代码

SortedDictionary<string, int> sortedScores = new SortedDictionary<string, int>();
sortedScores.Add("Evan", 38);
sortedScores.Add("Alice", 30);
// 会根据键排序，遍历输出 Alice: 30, Evan: 38
foreach (KeyValuePair<string, int> pair in sortedScores)
{
    Console.WriteLine($"{pair.Key}: {pair.Value}");
}