两个未排序数组中不在特定组合中的最小正整数

Question

两个未排序数组中不在特定组合中的最小正整数

algorithm

3

经典问题

给定一个未排序的整数数组 A，找到其中最小的未出现的正整数。

[3, 2, 1, 6, 5] -> 4
[2, 3, 4, 5] -> 1
[1, 2, 3, 4] -> 5

在这个经典问题中，你只有一个数组，可以找到很多关于这个问题的解决方案和资源，包括stackoverflow、Code Review@SE和geeksforgeeks.org。

困难版

在我的问题中，你会得到两个长度为N的数组A和B。构造一个长度为N的数组C，其最小缺失整数是最大的可能值。 C[i] 必须是 A[i] 或 B[i]。

A = [1, 2, 4, 3],
B = [1, 3, 2, 3] =->
C = [1, 2, 4, 3] 答案为 5

A = [4, 2, 1, 6, 5],
B = [3, 2, 1, 7, 7] =->
C = [3, 2, 1, 6, 5] 答案为 4

A = [2, 3],
B = [4, 5] =->
C = [2, 5] 答案为 1

我们如何使用最坏情况下时间和空间复杂度为O(N)来解决这个问题？

假设：

1<= N <= 100,000
1<= A[i], B[i] <= 100,000,000

- Eziz Durdyyev

1

为什么是-1，请告诉我？让我来解决这个问题。 - Eziz Durdyyev

1

一般人不喜欢只包含问题描述的帖子。就我个人而言，我认为这篇帖子没有任何问题。 - user202729

1

只有在做作业时才需要付出努力，请参见相关主题。 - user202729

1

在这种情况下，您应该链接到问题。虽然不是严格要求的（元），但我认为这是一个好习惯。（只是我的个人意见。我找不到任何元帖子，但回答者应该感觉您没有作弊） - user202729

1

@NourAlhadiMahmoud，我添加了限制条件。之前忘记写了，抱歉。 - Eziz Durdyyev

显示剩余11条评论

4个回答

1

如果您遍历数组并构建一个图，其中在A或B中遇到的每个唯一整数都成为一个顶点，并且每对整数A[i]和B[i]在两个顶点之间创建一条边，则此图最多将有2×N个顶点，因此此图占用的空间与N成线性关系。

然后，对于图中的每条边，我们将决定其方向，即将连接的两个整数中使用哪一个来创建C数组。最后，我们再次遍历数组，并针对每对整数，查看图中相应的边以知道使用哪个整数。

我认为决定图中边的方向所需的操作都可以在线性时间内完成（如果我错了，请纠正我），因此整个算法的时间和空间复杂度应为O(N)。

决定图中边的方向的规则如下：

图形的未连接部分将被单独处理。
如果一个（子）图形的边数少于顶点数（即它具有没有循环的树结构），则必须牺牲最高整数：将边指向该顶点，并将该方向传播到其余顶点。
如果一个（子）图形的边数多于顶点数（即它包含至少一个循环，可以是由多个边连接的两个顶点），则找到任何一个循环，并给其边赋予相同的方向（顺时针或逆时针）；然后将方向传播到其他顶点。

在迭代数组并查找图中对应的边时，当两个顶点多次连接时，请标记您已经使用过的整数，以便第二次使用另一个整数。之后，您可以选择任何一个整数。

例如：

A = [1,6,2,9,7,2,5,3,4,10]
B = [5,8,3,2,9,7,1,2,8,3]

图表：

1===5   6---8---4   9---2===3---10
                    |   |
                    --7--

我们找到了循环[1>5>1]和[9>2>7>9]，以及非循环子图中的最高整数8。

有向图：

1<=>5   6<--8-->4   9-->2<=>3-->10
                    ^   |
                    |-7<-

结果：

C = [1,6,2,2,9,7,5,3,4,10]

第一个缺失的整数是8，因为我们不得不牺牲它来拯救[6,8,4]子图中的4和6。

- m69 ''snarky and unwelcoming''

只有当所有数字都是正数时才正确，例如对于 A = [-2]，B = [1] 就会失败。 - user202729

@user202729 嗯，标题说的是“正整数”。 - m69 ''snarky and unwelcoming''

@user202729 这些示例表明假定输入为正数，但我可能是错误的。无论如何，这很容易修复。 - m69 ''snarky and unwelcoming''

1

输入都是正数，但只要算法对正整数正确就没问题。 - Eziz Durdyyev

这是我的建议。你的得分比用户202729高10倍，因此支持新晋会员会更好。你有什么看法？如果你是我，你会选择哪一个？ - Eziz Durdyyev

更不用说你们两个对新手都很友好了吧？ - Eziz Durdyyev

0

我尝试用Python3解决这个问题的方法。欢迎提出建议和反馈。谢谢。

从列表中删除负数值
将0插入列表中
使用sorted和set函数对列表进行排序并去除重复项
使用枚举器创建索引和值
从(0, 0)开始比较索引和值。如果索引和值不匹配，则下一个值为最小的正数。

--

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        #Remove all the negative values from the list
        positive_list = [i for i in nums if i > 0]

        #Appending Zero to list. In case of no postive values in the list.
        positive_list.append(0)

        #Sort and remove duplicates from the list using Sorted and set function
        sorted_postive_list = sorted(set(positive_list))

        #starting with (index, value) --> (0,0), Compare index and value, and if they don't match then next value should be the smallest positive number
        return next((a for a, b in enumerate(sorted_postive_list, sorted_postive_list[0]) if a != b), sorted_postive_list[-1]+1)

if __name__ == "__main__":
    num = [1,2,3,0]
    a = Solution()
    print(a.firstMissingPositive(num))

- Praveen Kumar

这并没有解决关于两个数组的任何问题。对于相关的经典问题，解决方案看起来很慢且未记录，但是很直接。 - greybeard

0

请检查这段Java 8代码片段。

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


public class Run {
    private int solution(int[] A) {

        List<Integer> positiveIntegerList = Arrays.stream(A).distinct().filter(e -> e > 0).boxed().sorted(Comparator.naturalOrder()).collect(Collectors.toList());
        final int i = 1;

        if (!positiveIntegerList.isEmpty()) {
            final int missingMax = positiveIntegerList.get(positiveIntegerList.size() - i) + i;
            List<Integer> range = IntStream.rangeClosed(i, positiveIntegerList.get(positiveIntegerList.size() - i))
                    .boxed().collect(Collectors.toList());

            AtomicInteger index = new AtomicInteger();
            return range.stream().filter(e -> !e.equals(positiveIntegerList.get(index.getAndIncrement()))).findFirst().
                    orElse(missingMax);
        } else {
            return i;
        }
    }


    public static void main(String[] args) {
        Run run = new Run();
        int[] intArray = new int[]{1, 3, 6, 4, 1, 2};
        System.out.println(run.solution(intArray));
    }
}

- Ajinkyad

2

你应该给你的解决方案添加一些说明。 - Eziz Durdyyev

你会注意到这并没有解决关于两个数组的任何问题。 - greybeard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user202729 · Accepted Answer

这个算法对数字范围内的数字进行了 O(n) 次算术运算，范围为 [0..n+2]，加上处理输入的时间。

将不在 [1..n] 范围内的所有数字替换为 n+2。这不会改变结果。
构建一个图，节点标记为 1, 2, 3, ..., n-1, n, n+2，对于所有的 0 <= i < n，存在一条从节点 A[i] 到 B[i] 的边（假设数组下标从 0 开始）。因此，该图有 n+1 个节点和 n 条边。

现在问题等价于找到一种方法来定向边，使得具有入度 0 的最小顶点尽可能大。

找到图中的连通分量。
对于每个具有 v 个顶点和 e 条边的连通分量，e >= v-1:
- 如果 e == v-1，那么它是一棵树。定向边的所有方式都将导致一个顶点具有入度 0，并且可以证明，对于树中的所有顶点，都存在一种定向边的方式，使得它是唯一具有入度 0 的顶点。
  
  方法：
  
  将该树以该顶点为根，然后使每条边从父节点指向子节点。
  
  当然，最优的做法是（贪心地）选择具有入度 0 的顶点为编号最大的顶点。
- 如果 e >= v，则连通分量内存在电路。然后，可以定向边以使所有顶点具有非零入度。
  
  证明（以及构造边方向的方法）留给读者自行思考。