力扣初級演算法（一）【陣列】
陣列問題在面試中出現頻率很高，你極有可能在面試中遇到，
我們推薦以下題目：只出現一次的數字，旋轉陣列，兩個陣列的交集 II 和 兩數之和，
136. 只出現一次的數字
難度：簡單
給定一個非空整數陣列，除了某個元素只出現一次以外，其余每個元素均出現兩次，找出那個只出現了一次的元素，
說明：
你的演算法應該具有線性時間復雜度， 你可以不使用額外空間來實作嗎？
示例 1:
輸入: [2,2,1] 輸出: 1示例 2:
輸入: [4,1,2,1,2] 輸出: 4
解題思路
-
樸素的想法是，遍歷這個陣列，并統計每個元素出現的次數，
然后找到那個出現次數為一的就好了，
-
用來統計個數的方法有很多，比如哈希表，這里給出LINQ的解法，
方法一：統計數量
public int SingleNumber(int[] nums)
=> nums.GroupBy(x => x).Where(x => x.Count() == 1).First().First();
-
我們還應該注意到，題目中表示，其他重復的元素只出現了兩次，
我們可以考慮使用集合添加移除元素，或者利用位運算的性質來解決問題
- 異或運算
- a ⊕ b = (?a ∧ b) ∨ (a ∧ ?b)
- 如果a、b兩個值不相同，則異或結果為1，如果a、b兩個值相同，異或結果為0，
- 異或運算滿足交換律和結合律，即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b
方法二：位運算
public int SingleNumber(int[] nums) => nums.Aggregate(0, (y, x) => y ^ x);
189. 旋轉陣列
難度：簡單
給定一個陣列，將陣列中的元素向右移動 k 個位置，其中 k 是非負數，
示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3 輸出: [5,6,7,1,2,3,4] 解釋: 向右旋轉 1 步: [7,1,2,3,4,5,6] 向右旋轉 2 步: [6,7,1,2,3,4,5] 向右旋轉 3 步: [5,6,7,1,2,3,4]示例 2:
輸入: [-1,-100,3,99] 和 k = 2 輸出: [3,99,-1,-100] 解釋: 向右旋轉 1 步: [99,-1,-100,3] 向右旋轉 2 步: [3,99,-1,-100]說明:
- 盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個問題，
- 要求使用空間復雜度為 O(1) 的 原地 演算法，
解題思路
- 樸素的想法是，模擬移動的程序，通過交換陣列中的元素來實作移動，
方法一：模擬
public void Rotate(int[] nums, int k)
{
k %= nums.Length;
for (int i = 0; i < k; i++)
{
var temp = nums[nums.Length - 1];
for (int j = nums.Length - 1; j > 0; j--)
nums[j] = nums[j - 1];
nums[0] = temp;
}
}
- 稍加觀察，不難發現，如果移動k個位置的話，對于陣列末尾的k個元素，一定被移動到了頭部，而剩下的元素依次右移，
- 也許我們可以有什么辦法把末尾的k個元素直接移到頭部，如果反轉一下陣列，那么尾部的k個元素剛好出現在了頭部，只不過順序和原來相反，
- 我們只需要對這k個元素和剩余的元素分別再反轉一次，讓他們恢復原來的順序即可，
方法二：反轉
public void Rotate(int[] nums, int k)
{
k %= nums.Length;
Array.Reverse(nums);
Array.Reverse(nums, 0, k);
Array.Reverse(nums, k, nums.Length - k);
}
350. 兩個陣列的交集 II
難度：簡單
給定兩個陣列，撰寫一個函式來計算它們的交集，
示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2] 輸出：[2,2]示例 2:
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 輸出：[4,9]說明：
- 輸出結果中每個元素出現的次數，應與元素在兩個陣列中出現次數的最小值一致，
- 我們可以不考慮輸出結果的順序，
進階：
- 如果給定的陣列已經排好序呢？你將如何優化你的演算法？
- 如果 nums1 的大小比 nums2 小很多，哪種方法更優？
- 如果 nums2 的元素存盤在磁盤上，記憶體是有限的，并且你不能一次加載所有的元素到記憶體中，你該怎么辦？
解題思路
-
樸素的想法是，比較兩個陣列，把相同的元素存放到一個新的容器當中，
值得注意的是，陣列中含有重復的元素，這里求交集的時候，要保留這些重復的元素，
可以把這些值型別的元素看做參考型別，兩個元素雖然值一樣，但應該被視為不同的參考，
-
基于這樣的想法，我們可以用哈希表來統計第一個陣列中元素出現的次數，
然后遍歷第二個陣列，如果元素在哈希表中，就加入到結果當中，同時哈希表對應的計數應該減一，
方法一：哈希表計數
public int[] Intersect(int[] nums1, int[] nums2)
{
// 選擇較短的陣列生成哈希表
if (nums1.Length > nums2.Length) return Intersect(nums2, nums1);
var res = new List<int>();
var dict = new Dictionary<int, int>();
foreach (var item in nums1)
dict[item] = dict.ContainsKey(item) ? dict[item] + 1 : 1;
foreach (var item in nums2)
if (dict.ContainsKey(item))
{
res.Add(item);
if (--dict[item] == 0) dict.Remove(item);
}
return res.ToArray();
}
思考
- 如果陣列已經有序，則可以考慮用雙指標同時遍歷兩個陣列，
1. 兩數之和
難度：簡單
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
示例:
給定 nums = [2, 7, 11, 15], target = 9 因為 nums[0] + nums[1] = 2 + 7 = 9 所以回傳 [0, 1]
解題思路
- 樸素的想法是，遍歷兩個陣列，如果任意兩個元素相加等于目標，就回傳這兩個元素的下標，
方法一：暴力列舉
public int[] TwoSum(int[] nums, int target)
{
for (int i = 0; i < nums.Length; i++)
for (int j = i + 1; j < nums.Length; j++)
if (nums[i] + nums[j] == target) return new int[] { i, j };
return null;
}
- 除此之外，我們還可以考慮雙指標的解法，
- 陣列有序的話，我們可以用兩個指標分別指向頭部和尾部，然后判斷兩數之和是否為目標，
- 如果大于目標，應該減小，將尾部指標前移，反之，將頭部指標右移，
- 如此反復，直到找到目標或雙指標相遇，
方法二：雙指標
public int[] TwoSum(int[] nums, int target)
{
var temp = nums.OrderBy(x => x).ToArray();
for (int i = 0, j = temp.Length - 1; i < j;)
{
int sum = temp[i] + temp[j];
if (sum > target) j--;
else if (sum < target) i++;
else return new int[]
{
Array.IndexOf(nums, temp[i]), Array.LastIndexOf(nums, temp[j])
};
}
return null;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/165299.html
標籤：C#