1、题目名称
Missing Number (缺失的数字)
2、题目地址
https:///problems/missing-number
3、题目内容
英文:Given an array containing n distinct numbers taken from 0, 1, 2, ..., n find the one that is missing from the array.
中文:给出一个包含了n个不同数字的数组,从0开始一直到n,找出缺失的数字。如果数组是连续的则返回n+1。
例如:给出的数组为 [0, 1, 3] 则返回2
4、解题方法1
第一种方法是对原数组进行排序,然后使用一个计数用的变量按序考察排序后的数组,如果数组的第n位不等于n,则返回n,否则返回数组长度加一。
一段实现本方法的Java代码为:
import java.util.Arrays;
/**
* 功能说明:LeetCode 268 - Missing Number
* 开发人员:Tsybius2014
* 开发时间:2015年8月25日
*/
public class Solution {
/**
* 找出丢掉的数字
* @param nums
* @return
*/
public int missingNumber(int[] nums) {
Arrays.sort(nums);
int counter;
for (counter = 0; counter < nums.length; counter++) {
if (counter != nums[counter]) {
return counter;
}
}
return counter;
}
}
5、解题方法2
第二种方法是建立一个新数组,长度为老数组的长度加一,新数组内的元素顺序排列。在老数组中每找到一个数字,都将新数组中对应位置变为-1,则最后新数组中未被变为-1的数字即为所求。
一段实现本方法的Java代码为:
/**
* 功能说明:LeetCode 268 - Missing Number
* 开发人员:Tsybius2014
* 开发时间:2015年8月25日
*/
public class Solution {
/**
* 找出丢掉的数字
* @param nums
* @return
*/
public int missingNumber(int[] nums) {
int[] nums2 = new int[nums.length + 1];
for (int i = 0; i < nums2.length; i++) {
nums2[i] = i;
}
for (int i = 0; i < nums.length; i++) {
nums2[nums[i]] = -1;
}
for (int i = 0; i < nums2.length; i++) {
if (nums2[i] != -1) {
return i;
}
}
return -1;
}
}
END
|