数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究编写一个Java程序，在一个给定的无序整数数组中找到缺失的正数。
假设我们给定一个无序整数数组。任务是在[0到n]范围内找到在给定数组中不存在的缺失的正数。例如：
输入-1 −
N = 9 arr = [0,2,5,9,1,7,4,3,6]
输出 −
8
说明 − 在给定的无序数组中，‘8’ 是唯一缺失的正整数，因此输出为 ‘8’。
输入-2 −
N = 1 arr = [0]
输出 −
1
说明 − 在给定的数组中，‘1’ 是唯一缺失的正整数，因此输出为 ‘1’。
解决这个问题的方法
有几种方法可以解决这个问题。但是，我们可以在线性时间O(n)和常数空间O(1)内解决这个问题。
因为我们知道我们的数组大小为n，并且它包含[0到n]范围内的元素。所以，如果我们对每个元素及其索引与'n'进行异或运算，那么我们可以找到缺失的唯一数字。
输入数组大小N，元素范围为[0到n]。
整数函数findMissingNumber(int arr[], int size)接收一个数组及其大小作为输入，并返回缺失的数字。
让我们用n作为缺失的数字来执行异或运算。
迭代所有数组元素，并对每个数组元素及其索引与缺失数字n执行异或运算。
现在返回缺失的数字。
示例
public class Solution {
public static int findMissingNumber(int arr[], int size){
int missing_no= size;
for(int i=0;i<size;i++){
missing_no^= i^arr[i];
}
return missing_no;
}
public static void main(String[] args){
int arr[] = {0,4,2,1,6,3};
int n = arr.length;
int a=findMissingNumber(arr, n);
System.out.println(a);
}
}输出
运行以上代码将生成以下输出：
5
在给定的数组{0,4,2,1,6,3}中，缺失的是'5'，因此我们将返回5。
更新于：2021年2月5日
500 次浏览
广告