268. Missing Number(缺失数字)
题目地址：https://leetcode.com/problems/missing-number/description/
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8说明: 你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
class Solution {
public int missingNumber(int[] nums) {
int sum = (nums.length + 1) * nums.length >>> 1; // 原本应该nums.length+1个数字，从0到nums.length，求和就行
int sum1 = 0;
for (int i = 0; i < nums.length; ++i) {
sum1 += nums[i];
}
return sum - sum1;
}
}
（CSDN的java模版是无法打出null的，不信你们去试试，反映给技术部无果，估计他们也解决不了）
Debug code in playground:
class Solution {
public int missingNumber(int[] nums) {
int sum = (nums.length + 1) * nums.length >>> 1;
int sum1 = 0;
for (int i = 0; i < nums.length; ++i) {
sum1 += nums[i];
}
return sum - sum1;
}
}
public class MainClass {
public static int[] stringToIntegerArray(String input) {
input = input.trim();
input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return new int[0];
}
String[] parts = input.split(",");
int[] output = new int[parts.length];
for(int index = 0; index < parts.length; index++) {
String part = parts[index].trim();
output[index] = Integer.parseInt(part);
}
return output;
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
int[] nums = stringToIntegerArray(line);
int ret = new Solution().missingNumber(nums);
String out = String.valueOf(ret);
System.out.print(out);
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-05-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读