用 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”进行XOR运算,那么我们可以找到作为数组中缺少的唯一数字的结果数字。
输入N大小的数组,元素在[0到n]范围内。
整数函数findMissingNumber(intarr[],intsize)将数组及其大小作为输入并返回缺失的数字。
让我们将n作为缺失的数字来执行XOR运算。
迭代所有数组元素并对每个数组元素及其相对于缺失数的索引执行XOR运算,即n
现在返回丢失的数字。
示例
public class Solution { public static int findMissingNumber(int arr[], int size){ int missing_no= size; for(int i=0;i输出结果 运行上面的代码将生成输出,
5在给定的数组{0,4,2,1,6,3}中,缺少'5',因此我们将返回5。