【剑指offer】03~05. 数组中的数字（C# 实现）

前言

😃 大家好，我是writer桑，这是自己整理的 C# 做题记录，方便自己学习的同时分享出来，感谢支持。

---

03. 数组中重复的数字

题目描述：

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

代码实现：

public class Solution
{public int FindRepeatNumber(int[] nums){HashSet<int> set = new HashSet<int> { };    // 声明一个空的哈希表 foreach (int num in nums){if (set.Contains(num))      // 重复包含直接返回 return num;elseset.Add(num);           // 无包含则添加 }return 0;}
}

思路分析：

• 首先创建一个容器，遍历数组中的每个数字并检查容器中有无这个数字， 如果没有则直接放入元素， 如果有则证明这个元素是重复的可直接返回。
• 这里的容器推荐使用哈希表（HashSet）， 因为哈希表的查找效率很高，可以很好的提高整个算法的效率。

代码实现2：

public class Solution {public int FindRepeatNumber(int[] nums) {Array.Sort(nums);	// 循环遍历for (int i = 1; i < nums.Length; i++) 	// 对数组进行排序 {if (nums[i] == nums[i - 1])return nums[i];}return 0;  }
}

思路分析：

• 对数组进行排序，for 循环从第二个元素开始遍历数组，如果与前一个元素相等则可以证明该元素是重复的。
• 因为需要多执行数组排序这一步，所以性能没有第一种解法高，推荐第一种解法。

04. 二维数组中的查找

题目描述：

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

现有矩阵 matrix 如下：
[
   [1, 4, 7, 11, 15],
   [2, 5, 8, 12, 19],
   [3, 6, 9, 16, 22],
   [10, 13, 14, 17, 24],
   [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。
给定 target = 20，返回 false。

代码实现：

public class Solution {public bool FindNumberIn2DArray(int[][] matrix, int target) {if (matrix.Length == 0 || matrix == null)	// 判断是否为空 return false; int i = matrix.Length - 1;int j = 0;while (i >= 0 && j < matrix[0].Length){if (matrix[i][j] > target)i--;else if (matrix[i][j] < target)j++;elsereturn true;}return false;   }
}

思路分析：

• 将矩阵逆时针旋转 45° 并展开，可以发现类似于二叉搜索树， 那么从根节点开始搜索时，遇到比 target 大的元素就向左，反之则向右，以此来找到目标值 target 。
• 需要事先判断 matrix 是否为空，为空直接返回 false 。根据二叉搜索树的特性，选用矩阵的左下角的元素作为标志数 flag，若 flag > target ，则 target 一定在 flag 所在 行的上方, 若 flag < target ，则 target 一定在 flag 所在 列的右方，以此类推直到找到目标数 target 。
• 算法本身比较好理解，难点在于根据题目的描述找到突破口。

代码实现2：

public class Solution {public bool FindNumberIn2DArray(int[][] matrix, int target) {foreach (int[] arr in matrix){if(arr.Contains(target))	// 包含直接返回true{return true; }}return false; }
}

思路分析：

• 简单的循环输出，逐个数组进行判断有无包含目标数，有则直接返回 true 。当循环结束时，也即表示没有该目标数，返回 false 。
• 对比第一种解法，代码量更少， 但是因为每次都需要逐个遍历数组，所以性能较低，推荐第一种解法。

05. 替换空格

题目实现：

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例：

输入：s = “We are happy.”
输出：“We%20are%20happy.”

代码实现：

public class Solution {public string ReplaceSpace(string s) {return string.Join("%20",s.Split(' ')); }
}

思路分析：

• 使用 Split 方法指定空格 ’ ’ 进行分割，再利用 Join 方法指定 “%20” 进行连接， 然后直接返回即可。
• 这种解法很容易想到，而且代码量很少、很简洁，一行代码搞定。

代码实现2：

public class Solution {public string ReplaceSpace(string s) {StringBuilder res = new StringBuilder();        // 声明可变字符串foreach(var c in s)         // 循环遍历 {if(c == ' ')res.Append("%20");else res.Append(c);      }return res.ToString(); }
}

思路分析：

• 声明可变字符串 res 用于存放返回结果，for 循环遍历字符串 s 依次判断字符元素， 如果为空格 ’ ’ 则替换为"%20"放入 res , 如果不为空格则直接放入 res 中。循环结束则直接将 res 转换为字符串类型返回即可。
• 与第一种解法相比，这种解法更常见，代码量较多，两者在性能上差不多。

---

结语

🌻 以上就是本次的做题记录啦，希望大家看完有所收获。同时希望大家多多支持，你们的支持就是笔者学习最大的动力！