算法找出最小的非负整数，名单中没有 [英] Algorithm to find the smallest non negative integer that is not in a list

问题描述

由于整数列表，我如何能最好地找到一个整数，它的没有的列表？

Given a list of integers, how can I best find an integer that is not in the list?

该列表可能会非常大，而整数可能很大（即BigIntegers，不只是32位整数）。

The list can potentially be very large, and the integers might be large (i.e. BigIntegers, not just 32-bit ints).

如果这有什么差别，名单是可能来分类，即99％的时间将被排序，但我不能依靠总是被排序。

If it makes any difference, the list is "probably" sorted, i.e. 99% of the time it will be sorted, but I cannot rely on always being sorted.

修改 -

要澄清，给出的列表{0，1，3，4，7}，可接受的溶液的例子可以是-2，2,8和10012，但我preFER找到最小的，非负溶液（即2），如果有一个算法，可以找到它，而无需整个列表进行排序。

To clarify, given the list {0, 1, 3, 4, 7}, examples of acceptable solutions would be -2, 2, 8 and 10012, but I would prefer to find the smallest, non-negative solution (i.e. 2) if there is an algorithm that can find it without needing to sort the entire list.

推荐答案

一个简单的方法是将遍历列表，以获得最高值 N ，那么你就知道 N + 1 不在列表中。

One easy way would be to iterate the list to get the highest value n, then you know that n+1 is not in the list.

编辑：

要找到最小的正未使用的编号方法是从零开始和扫描列表的数量，重新开始加大，如果您发现该号码。为了使之更有效率，并利用该列表的概率高进行排序，你可以移动，比当前小到列表中的未使用部分的数字。

A method to find the smallest positive unused number would be to start from zero and scan the list for that number, starting over and increase if you find the number. To make it more efficient, and to make use of the high probability of the list being sorted, you can move numbers that are smaller than the current to an unused part of the list.

此方法使用列表为较低的数字存储空间的开始，的startIndex 变量跟踪，其中有关数字启动：

This method uses the beginning of the list as storage space for lower numbers, the startIndex variable keeps track of where the relevant numbers start:

public static int GetSmallest(int[] items) {
	int startIndex = 0;
	int result = 0;
	int i = 0;
	while (i < items.Length) {
		if (items[i] == result) {
			result++;
			i = startIndex;
		} else {
			if (items[i] < result) {
				if (i != startIndex) {
					int temp = items[startIndex];
					items[startIndex] = items[i];
					items[i] = temp;
				}
				startIndex++;
			}
			i++;
		}
	}
	return result;
}

我做，我创建的列表100000随机数从0到19999性能测试，这使得平均最低人数在150左右在测试运行（与1000测试列出每个），该方法发现的最小数字排序的名单在0.32毫秒平均在8.2毫秒，并且由平均有序列表。

I made a performance test where I created lists with 100000 random numbers from 0 to 19999, which makes the average lowest number around 150. On test runs (with 1000 test lists each), the method found the smallest number in unsorted lists by average in 8.2 ms., and in sorted lists by average in 0.32 ms.

（我还没有在该方法离开列表什么状态，因为它可能会掉在它的一些项目进行检查。它的叶子含有相同的物品，至少，并且因为它的动作较小的值向下列表，我认为该列表它实际上应该更加有序为每个搜索。）

(I haven't checked in what state the method leaves the list, as it may swap some items in it. It leaves the list containing the same items, at least, and as it moves smaller values down the list I think that it should actually become more sorted for each search.)

这篇关于算法找出最小的非负整数，名单中没有的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！