个人github：https://github.com/xiongAlen?tab=repositories
<h2 id="1">1.leetcode 268. 缺失数字 </h2>
题目描述：
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
思路1：排序。
分析：首先对数组进行排序，然后对顺序数组双端进行检查，即：判断0是否在数组首位，n是否在数组末尾。若两种情况都满足，则确实数字在0-n之间。最后遍历数组即可。
代码（来自官方题解）
class Solution {
public int missingNumber(int[] nums) {
//排序
Arrays.sort(nums);
// 判断 n 是否出现在末位
if (nums[nums.length-1] != nums.length) {
return nums.length;
}
// 判断 0 是否出现在首位
else if (nums[0] != 0) {
return 0;
}
// 此时缺失的数字一定在 (0, n) 中
for (int i = 1; i < nums.length; i++) {
int expectedNum = nums[i-1] + 1;
if (nums[i] != expectedNum) {
return expectedNum;
}
}
// 未缺失任何数字（保证函数有返回值）
return -1;
}
}
思路2：n项和
分析：求n项和减去数组累加和即是所求数。
代码：
class Solution {
public int missingNumber(int[] nums) {
int result = 0;
len=nums.length；
for (int i = 1; i <= len; i++) {
result += i - nums[i-1];
}
return result;
}
}
<h2 id="2">2.leetcode 287. 寻找重复数 </h2>
题目描述：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
思路1：集合
分析：将数组中的数放入集合中（Set），并检查该数是否已存在于集合。若是，则返回该数。
代码：
class Solution {
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for (int num : nums) {
if (set.contains(num)) {
return num;
}
set.add(num);
}
return -1;
}
}
思路2：快慢指针
预备知识：
运用快慢指针寻找循环链表入口节点。
分析：本题可将数组配合下标，抽象称为寻找循环链表入口的问题。例如数组a=[1, 3, 4, 2, 5, 4];元素1的下一个节点为对应数组下标为1的元素。这样抽象成链表list:1->3->2->4->5->4(进入循环);
代码：
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
while(slow != fast || fast == 0){
slow = nums[slow];
fast = nums[nums[fast]];
}
//慢指针指向起点
slow = 0;
while(fast != slow){
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
}
<h2 id="3">3.leetcode 41. 缺失的第一个正数 </h2>
题目描述：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
思路：桶排序
分析：将数组中的元素打散，并归置于原数组，打散的规则是：将i放于下标为i-1的位置。这样排序后，遍历找出不符合规则的元素，返回其下标+1即所得。
代码：
public class Solution {
// 关键字：桶排序，什么数字就要放在对应的索引上，其它空着就空着
// 最好的例子：[3,4,-1,1]
// 整理好应该是这样：[1,-1,3,4]，
// 这里 1，3，4 都在正确的位置上，
// -1 不在正确的位置上，索引是 1 ，所以返回 2
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 注意：先判断给数是否能够构成索引。
// 再判断该数对应索引的位置上是否为这个数
// 即 nums[i] ?= nums[nums[i]-1] 这里要特别小心
while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
// 第 3 个条件不成立的索引的部分是 i 和 nums[i]-1
swap(nums, nums[i] - 1, i);
}
}
for (int i = 0; i < len; i++) {
// [1,-2,3,4]
// 除了 -2 其它都满足： i+1 = num[i]
if (nums[i] - 1 != i) {
return i + 1;
}
}
return len + 1;
}
private void swap(int[] nums, int index1, int index2) {
nums[index1] = nums[index1] ^ nums[index2];
nums[index2] = nums[index1] ^ nums[index2];
nums[index1] = nums[index1] ^ nums[index2];
}
}
优化：上述代码采用位运算交换两元素，替换了加减交换的做法。
网友评论