英文:
Return the lowest positive integer value not contained in an int[] array, optimized for performance
问题
我正在进行在线评估，以返回数组中不在整数数组中的最小正值。
我使用了这段代码：
class Solution
{
public static int solution(int[] A)
{
int hold = 1;
while (A.Contains(hold))
{
hold++;
}
return hold;
}
}
它能够正常工作，并且在正确性方面获得了100%的分数，但在效率方面只得到了25%。如何能够使它更加高效？该网站规定测试数组的大小可达100,000个值。我的编程技能在WinForms之外有所欠缺，我将不胜感激地接受任何帮助，以使我的代码更加高效。
一个示例测试案例是 `[1, 3, 6, 4, 1, 2]`，预期返回值为 `5`。
英文:
I was doing an assessment online to return the lowest positive value of an int not in the array.
I used this code:
class Solution
{
public static int solution(int[] A)
{
int hold = 1;
while (A.Contains(hold))
{
hold++;
}
return hold;
}
}
It works and received 100% for correctness however got 25% for efficiency. How can I make this more efficient? The website states that the testing can be of an array up to 100,000 values. My coding skills outside of WinForms are lacking and I would appreciate any help in order to make my code more efficient.
An example test would be [1, 3, 6, 4, 1, 2], and it would return 5.
答案1
得分: 2
以下是您要翻译的代码部分：
这段代码测试是否存在一个连续的正整数，因此您可以首先对数组进行排序，然后找到不连续的位置。
public static int solution(int[] A)
{
Array.Sort(A);
var j = Array.IndexOf(A, 1);
if (j < 0)
return 1;
int k = 1;
for (int i = j + 1; i < A.Length; i++)
{
if (A[i] - k > 1)
break;
k = A[i];
}
return k + 1;
}
请注意，我只提供了代码的翻译部分。如果您需要进一步的解释或帮助，请随时提问。
英文:
This code tests whether a continuous positive integer exists, so you can sort the array first, then find out the discontinuous position.
public static int solution(int[] A)
{
Array.Sort(A);
var j = Array.IndexOf(A, 1);
if (j < 0)
return 1;
int k = 1;
for (int i = j + 1; i < A.Length; i++)
{
if (A[i] - k > 1)
break;
k = A[i];
}
return k + 1;
}
答案2
得分: 1
最简单的更改是将数组转换为 HashSet<int>。这将将查找时间 A.Contains(hold) 从 O(n) 减少到近似 O(1)：
public static int solution(int[] A)
{
var hashSet = new HashSet<int>(A);
int hold = 1;
while (hashSet.Contains(hold))
{
hold++;
}
return hold;
}
英文:
The easiest change would be to turn the array into a HashSet<int>. This reduces the lookup time A.Contains(hold) from O(n) to essentially O(1):
public static int solution(int[] A)
{
var hashSet = new HashSet<int>(A);
int hold = 1;
while (hashSet.Contains(hold))
{
hold++;
}
return hold;
}
答案3
得分: 0
以下是LINQ方法。它可能不如其他答案中的解决方案快，但可能会更加简洁：
public static int GetLowestPositiveNumberNotContained(int[] array)
{
return array
.Where(n => n > 0)
.Distinct()
.Order()
.Append(-1)
.Zip(Enumerable.Range(1, Array.MaxLength + 1))
.First(e => e.First != e.Second)
.Second;
}
解释：
- 我们过滤掉数组中的非正数。
- 我们过滤掉重复项。
- 我们对筛选后的查询（数组中唯一的正数）进行排序。
- 我们在末尾添加一个负数（哨兵），以防止“掉进地中海”。
- 我们通过将查询（排序后的唯一正数）与从
1开始的递增序列进行压缩，创建成对的数字。 - 我们找到第一个有非相等成员的对。
- 这个对的第二个成员就是我们要寻找的数字。它是数组中不包含的最小正数。
在线演示。
英文:
Here is a LINQ approach. It's unlikely to be as fast as the solutions in the other answers. It might be a bit cuter though:
public static int GetLowestPositiveNumberNotContained(int[] array)
{
return array
.Where(n => n > 0)
.Distinct()
.Order()
.Append(-1)
.Zip(Enumerable.Range(1, Array.MaxLength + 1))
.First(e => e.First != e.Second)
.Second;
}
Explanation:
- We filter out the non-positive numbers in the array.
- We filter out the duplicates.
- We sort the filtered query (unique positive numbers in the array).
- We append a negative number (sentinel) at the end, so that we don't fall into the Mediterranean sea.
- We create pairs by zipping the query (sorted unique positive numbers), with an incremental sequence of numbers that starts from
1. - We find the first pair having non-equal members.
- The second member of this pair is the number that we are searching for. It's the lowest positive number not contained in the array.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论