7

LeetCode-268-丢失的数字

 2 years ago
source link: https://segmentfault.com/a/1190000040679141
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

LeetCode-268-丢失的数字

丢失的数字

题目描述:给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶:

  • 你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:数组遍历

首先,获取数字的长度为n,根据根据公式n*(n+1)/2得到从0到n的数字相加之和为sum,由于nums数组中只缺少一个数,所以遍历数组,将sum减去数组中所有的元素,然后剩下的数字就是要返回的数。

public class LeetCode_268 {
    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = n * (n + 1) / 2;
        for (int num : nums) {
            sum -= num;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println(missingNumber(nums));
    }
}

【每日寄语】 最清晰的脚印,总是印在最泥泞的路上。


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK