力扣初级算法（一）【数组】

数组问题在面试中出现频率很高，你极有可能在面试中遇到。

我们推荐以下题目：只出现一次的数字，旋转数组，两个数组的交集 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;}

原文转载：http://www.shaoqun.com/a/480873.html

topia：https://www.ikjzd.com/w/2741

乐一番：https://www.ikjzd.com/w/1562

米兰网：https://www.ikjzd.com/w/1304.html

力扣初级算法（一）【数组】数组问题在面试中出现频率很高，你极有可能在面试中遇到。我们推荐以下题目：只出现一次的数字，旋转数组，两个数组的交集II和两数之和。136.只出现一次的数字难度：简单给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？示例1:输入:[2,2,1]输出:1示例
topia：https://www.ikjzd.com/w/2741
黄远：https://www.ikjzd.com/w/1785
亚马逊PPC广告的设置技巧：https://www.ikjzd.com/home/124
注册新加坡公司有哪些优势？需要什么条件？：https://www.ikjzd.com/home/19045
拥有3000时尚大V的潮牌电商在纽交所上市了！：https://www.ikjzd.com/home/98217