问题来自于Codility编程训练，它听起来如下：我们有一个数组（A []），其中n（范围从1到100,000）元素，这些是我们的参数。数组的元素是从-2,147,483,648到2,147,483,647的整数，我们需要找到数组中不存在的最小正整数。当然，这可以在O（n * log n）中轻松完成，方法是将它们全部排序并通过排序数组，查找缺少的正数（这个最后一个操作在我的解决方案中具有O（n）最差的时间复杂度）。但根据Codility的说法，这个整体问题可以在O（n）中完成，我看不出有任何办法可以做到这一点。有人可以提供一些技巧让我不被卡住吗？
PS这是一个链接，详细描述了我不允许复制的问题 - https://codility.com/c/intro/demo35UEXH-EAT
根据鸽子原理，数字1,2，...，n + 1中的至少一个不在阵列中。让我们创建一个大小为n + 1的布尔数组b来存储这些数字是否存在。
现在，我们处理输入数组。如果我们找到从1到n + 1的数字，我们在b中标记相应的条目。如果我们看到的数字不符合这些范围，只需丢弃它并继续下一个。两种情况都是每个输入条目O（1），总O（n）。
在我们完成输入处理之后，我们可以在O（n）中找到我们的布尔数组b中的第一个非标记条目。
JavaScript 100％
function solution(A) {
let sortedOb = {};
let biggest = 0;
A.forEach(el => {
if (el > 0) {
sortedOb[el] = 0;
biggest = el > biggest ? el : biggest;
}
});
let arr = Object.keys(sortedOb).map(el => +el);
if (arr.length == 0) return 1;
for(let i = 1; i <= biggest; i++) {
if (sortedOb[i] === undefined) return i;
}
return biggest + 1;
}
我相信解决方案比使用n（100,000）元素的布尔数组“标记”相应值更复杂。大小为n的布尔数组不会“直接”映射到可能的值范围（-2,147,483,648到2,147,483,647）。我编写的这个Java示例尝试通过根据值与最大值的偏移量映射值来映射100K行。它还执行模数以将得到的数组减小到与样本元素长度相同的大小。
/**
*
* This algorithm calculates the values from the min value and mods this offset with the size of the 100K sample size.
* This routine performs 3 scans.
* 1. Find the min/max
* 2. Record the offsets for the positive integers
* 3. Scan the offsets to find missing value.
*
* @author Paul Goddard
*
*/
public class SmallestPositiveIntMissing {
static int ARRAY_SIZE = 100000;
public static int solve(int[] array) {
int answer = -1;
Maxmin maxmin = getMaxmin(array);
int range = maxmin.max - maxmin.min;
System.out.println("min: " + maxmin.min);
System.out.println("max: " + maxmin.max);
System.out.println("range: " + range);
Integer[] values = new Integer[ARRAY_SIZE];
if (range == ARRAY_SIZE) {
System.out.println("No gaps");
return maxmin.max + 1;
}
for (int val: array) {
if (val > 0) {
int offset = val - maxmin.min;
int index = offset % ARRAY_SIZE;
values[index] = val;
}
}
for (int i = 0; i < ARRAY_SIZE; i++) {
if (values[i] == null) {
int missing = maxmin.min + i;
System.out.println("Missing: " + missing);
answer = missing;
break;
}
}
return answer;
}
public static Maxmin getMaxmin(int[] array) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int val:array) {
if (val >=0) {
if (val > max) max = val;
if (val < min) min = val;
}
}
return new Maxmin(max,min);
}
public static void main(String[] args) {
int[] A = arrayBuilder();
System.out.println("Min not in array: " + solve(A));
}
public static int[] arrayBuilder() {
int[] array = new int[ARRAY_SIZE];
Random random = new Random();
System.out.println("array: ");
for (int i=0;i < ARRAY_SIZE; i++) {
array[i] = random.nextInt();
System.out.print(array[i] + ", ");
}
System.out.println(" array done.");
return array;
}
}
class Maxmin {
int max;
int min;
Maxmin(int max, int min) {
this.max = max;
this.min = min;
}
}
100％：Python排序程序不被视为作弊......
def solution(A):
"""
Sort the array then loop till the value is higher than expected
"""
missing = 1
for elem in sorted(A):
if elem == missing:
missing += 1
if elem > missing:
break
return missing
Sweet Swift版本。 100％正确
public func solution(inout A : [Int]) -> Int {
//Create a Hash table
var H = [Int:Bool]()
// Create the minimum possible return value
var high = 1
//Iterate
for i in 0..<A.count {
// Get the highest element
high = A[i] > high ? A[i] : high
// Fill hash table
if (A[i] > 0){
H[A[i]] = true
}
}
// iterate through possible values on the hash table
for j in 1...high {
// If you could not find it on the hash, return it
if H[j] != true {
return j
} else {
// If you went through all values on the hash
// and can't find it, return the next higher value
// e.g.: [1,2,3,4] returns 5
if (j == high) {
return high + 1
}
}
}
return high
}
它对我有用。它不是O（n），但更简单：
import java.util.stream.*;
class Solution {
public int solution(int[] A) {
A = IntStream.of(A)
.filter(x->x>0)
.distinct()
.sorted()
.toArray();
int min = 1;
for(int val : A)
{
if(val==min)
min++;
else
return min;
}
return min;
}
}
int[] copy = new int[A.length];
for (int i : A)
{
if (i > 0 && i <= A.length)
{
copy[i - 1] = 1;
}
}
for (int i = 0; i < copy.length; i++)
{
if (copy[i] == 0)
{
return i + 1;
}
}
return A.length + 1;
斯威夫特3 - 100％
public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 3.0 (Linux)
var solution = 1
var hashSet = Set<Int>()
for int in A
{
if int > 0
{
hashSet.insert(int)
while hashSet.contains(solution)
{
solution += 1
}
}
}
return solution
}
感谢Marian的回答。
这是我使用python的解决方案：
def solution(A):
m = max(A)
if m <= 0:
return 1
if m == 1:
return 2
# Build a sorted list with all elements in A
s = sorted(list(set(A)))
b = 0
# Iterate over the unique list trying to find integers not existing in A
for i in xrange(len(s)):
x = s[i]
# If the current element is lte 0, just skip it
if x <= 0:
continue;
b = b + 1
# If the current element is not equal to the current position,
# it means that the current position is missing from A
if x != b:
return b
return m + 1
得分100％/ 100％https://codility.com/demo/results/demoDCU7CA-SBR/
这是我的解决方案是Swift 4
public func solution(_ A: inout [Int]) -> Int {
var minNum = 1
var hashSet = Set<Int>()
for int in A {
if int > 0 {
hashSet.insert(int)
}
}
while hashSet.contains(minNum) {
minNum += 1
}
return minNum
}
var array = [1,3,6]
solution(&array)
//答案：2
javascript 100％100％首先对数组进行排序，你只需要扫描正元素，找到1的索引（如果数组中没有1，那么答案是1）。然后在1之后搜索元素直到找到缺失的数字。
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var missing = 1;
// sort the array.
A.sort(function(a, b) { return a-b });
// try to find the 1 in sorted array if there is no 1 so answer is 1
if ( A.indexOf(1) == -1) { return 1; }
// just search positive numbers to find missing number
for ( var i = A.indexOf(1); i < A.length; i++) {
if ( A[i] != missing) {
missing++;
if ( A[i] != missing ) { return missing; }
}
}
// if cant find any missing number return next integer number
return missing + 1;
}
Java中的100％简单解决方案
public static int solution(final int[] A)
{
Arrays.sort(A);
int min = 1;
// Starting from 1 (min), compare all elements, if it does not match
// that would the missing number.
for (int i : A) {
if (i == min) {
min++;
}
}
return min;
}
~
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int i;
bool *bin = (bool *)calloc((N+1),sizeof(bool));
for (i = 0; i < N; i++)
{
if (A[i] > 0 && A[i] < N+1)
{
bin[A[i]] = true;
}
}
for (i = 1; i < N+1; i++)
{
if (bin[i] == false)
{
break;
}
}
return i;
}
可能会有帮助，我使用算术级数来计算总和，并使用二进制searach获取元素。检查几百个值的数组工作良好。因为在步骤2中有一个用于循环和压缩，O（n / 2）或更少
def Missingelement (A):
B = [x for x in range(1,max(A)+1,1)]
n1 = len(B) - 1
begin = 0
end = (n1)//2
result = 0
print(A)
print(B)
if (len(A) < len(B)):
for i in range(2,n1,2):
if BinSum(A,begin,end) > BinSum(B,begin,end) :
end = (end + begin)//2
if (end - begin) <= 1 :
result=B[begin + 1 ]
elif BinSum(A,begin,end) == BinSum(B,begin,end):
r = end - begin
begin = end
end = (end + r)
if begin == end :
result=B[begin + 1 ]
return result
def BinSum(C,begin,end):
n = (end - begin)
if end >= len(C):
end = len(C) - 1
sum = n*((C[begin]+C[end])/2)
return sum
def main():
A=[1,2,3,5,6,7,9,10,11,12,14,15]
print ("smallest number missing is ",Missingelement(A))
if __name__ == '__main__': main()
事实上，C代码可用于任何编程语言而无需对逻辑进行任何更改。
逻辑是N数的总和是N*(N+1)/2。
int solution(int A[], int N) {
// write your code in C99
long long sum=0;
long long i;
long long Nsum=0;
for(i=0;i<N;i++){
sum=sum + (long long)A[i];
}
if (N%2==0){
Nsum= (N+1)*((N+2)/2);
return (int)(Nsum-sum);
}
else{
Nsum= ((N+1)/2)*(N+2);
return (int)(Nsum-sum);
}
}
这给了100/100分。
该解决方案在测试中获得100/100：
class Solution {
public int solution(int[] A) {
int x = 0;
while (x < A.length) {
// Keep swapping the values into the matching array positions.
if (A[x] > 0 && A[x] <= A.length && A[A[x]-1] != A[x]) {
swap(A, x, A[x] - 1);
} else {
x++; // Just need to increment when current element and position match.
}
}
for (int y=0; y < A.length; y++) {
// Find first element that doesn't match position.
// Array is 0 based while numbers are 1 based.
if (A[y] != y + 1) {
return y + 1;
}
}
return A.length + 1;
}
private void swap (int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
PHP https://codility.com/demo/results/trainingKFXWKW-56V/ 100％
function solution($A){
$A = array_unique($A);
sort($A);
if (empty($A)) return 1;
if (max($A) <= 0) return 1;
if (max($A) == 1) return 2;
if (in_array(1, $A)) {
$A = array_slice($A, array_search(1, $A)); // from 0 to the end
array_unshift($A, 0); // Explanation 6a
if ( max($A) == array_search(max($A), $A)) return max($A) + 1; // Explanation 6b
for ($i = 1; $i <= count($A); $i++){
if ($A[$i] != $i) return $i; // Explanation 6c
}
} else {
return 1;
}
}
//解释
这是我的解决方案，评估收益率为88％ - 时间为O（n），正确度为100％，性能为75％。记住 - 可能有一个所有负数的数组，或超过100,000的数字。大多数上述解决方案（使用实际代码）产生的分数要低得多，或者只是不起作用。其他人似乎与Codility上提出的Missing Integer问题无关。
int compare( const void * arg1, const void * arg2 )
{
return *((int*)arg1) - *((int*)arg2);
}
solution( int A[], int N )
{
// Make a copy of the original array
// So as not to disrupt it's contents.
int * A2 = (int*)malloc( sizeof(int) * N );
memcpy( A2, A1, sizeof(int) * N );
// Quick sort it.
qsort( &A2[0], N, sizeof(int), compare );
// Start out with a minimum of 1 (lowest positive number)
int min = 1;
int i = 0;
// Skip past any negative or 0 numbers.
while( (A2[i] < 0) && (i < N )
{
i++;
}
// A variable to tell if we found the current minimum
int found;
while( i < N )
{
// We have not yet found the current minimum
found = 0;
while( (A2[i] == min) && (i < N) )
{
// We have found the current minimum
found = 1;
// move past all in the array that are that minimum
i++;
}
// If we are at the end of the array
if( i == N )
{
// Increment min once more and get out.
min++;
break;
}
// If we found the current minimum in the array
if( found == 1 )
{
// progress to the next minimum
min++;
}
else
{
// We did not find the current minimum - it is missing
// Get out - the current minimum is the missing one
break;
}
}
// Always free memory.
free( A2 );
return min;
}
我的100/100解决方案
public int solution(int[] A) {
Arrays.sort(A);
for (int i = 1; i < 1_000_000; i++) {
if (Arrays.binarySearch(A, i) < 0){
return i;
}
}
return -1;
}
static int spn(int[] array)
{
int returnValue = 1;
int currentCandidate = 2147483647;
foreach (int item in array)
{
if (item > 0)
{
if (item < currentCandidate)
{
currentCandidate = item;
}
if (item <= returnValue)
{
returnValue++;
}
}
}
return returnValue;
}
构建所有值的哈希表。对于数字1到n + 1，检查它们是否在哈希表中。其中至少有一个不是。打印出最低的这个数字。
这是O（n）预期时间（你可以得到with high probability）。请参阅@ Gassa的答案，了解如何避免哈希表支持大小为O（n）的查找表。
今天写了这个，得到了100/100。不是最优雅的解决方案，但易于理解 -
public int solution(int[] A) {
int max = A.length;
int threshold = 1;
boolean[] bitmap = new boolean[max + 1];
//populate bitmap and also find highest positive int in input list.
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && A[i] <= max) {
bitmap[A[i]] = true;
}
if (A[i] > threshold) {
threshold = A[i];
}
}
//find the first positive number in bitmap that is false.
for (int i = 1; i < bitmap.length; i++) {
if (!bitmap[i]) {
return i;
}
}
//this is to handle the case when input array is not missing any element.
return (threshold+1);
}
简单的Java源。正确性和性能得分为100/100。
public int solution(int[] A) {
int smallestMissingInteger = 1;
if (A.length == 0) {
return smallestMissingInteger;
}
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
set.add(A[i]);
}
}
while (set.contains(smallestMissingInteger)) {
smallestMissingInteger++;
}
return smallestMissingInteger;
}
public int solutionMissingInteger(int[] A) {
int solution = 1;
HashSet<Integer> hashSet = new HashSet<>();
for(int i=0; i<A.length; ++i){
if(A[i]<1) continue;
if(hashSet.add(A[i])){
//this int was not handled before
while(hashSet.contains(solution)){
solution++;
}
}
}
return solution;
}
100％Javascript
function solution(A) {
// write your code in JavaScript (Node.js 4.0.0)
var max = 0;
var array = [];
for (var i = 0; i < A.length; i++) {
if (A[i] > 0) {
if (A[i] > max) {
max = A[i];
}
array[A[i]] = 0;
}
}
var min = max;
if (max < 1) {
return 1;
}
for (var j = 1; j < max; j++) {
if (typeof array[j] === 'undefined') {
return j
}
}
if (min === max) {
return max + 1;
}
}
C＃得分100％，
说明：使用查找表，我们在输入数组中存储已经看到的值，我们只关心输入数组大于0且小于或等于长度的值
public static int solution(int[] A)
{
var lookUpArray = new bool[A.Length];
for (int i = 0; i < A.Length; i++)
if (A[i] > 0 && A[i] <= A.Length)
lookUpArray[A[i] - 1] = true;
for (int i = 0; i < lookUpArray.Length; i++)
if (!lookUpArray[i])
return i + 1;
return A.Length + 1;
}
我的解决方案100％。在Java中。
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { public int solution(int[] A) { Arrays.sort(A); ArrayList<Integer> positive = new ArrayList<>(); for (int i = 0; i < A.length; i++) { if(A[i] > 0) positive.add(A[i]); } if(positive.isEmpty()) return 1; if(positive.get(0) > 1) return 1; for(int i = 0; i < positive.size() - 1; i++) { if(positive.get(i + 1) - positive.get(i) > 1) return positive.get(i) + 1; } return positive.get(positive.size() - 1) + 1; } public static void main(String[] args) { Solution solution = new Solution(); int[] A = {-5,1,2,3,4,6,7,8,9,5}; System.out.println(solution.solution(A)); } }