相关疑难解决方法(0)

这是一个面试问题:

给定一个包含40亿个整数的输入文件,提供一个算法来生成一个未包含在文件中的整数.假设您有1 GB内存.如果您只有10 MB内存,请跟进您的操作.

我的分析:

文件大小为4×10 ⁹ ×4字节= 16 GB.

我们可以进行外部排序,因此我们可以了解整数的范围.我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？

我的理解(阅读完所有答案后):

假设我们正在讨论32位整数.有2 ^ 32 = 4*10 ^9个不同的整数.

情况1:我们有1 GB = 1*10 ⁹*8位= 80亿位内存.解决方案:如果我们使用一个代表一个不同整数的位,那就足够了.我们不需要排序.执行:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

情况2:10 MB内存= …

我最近在某个地方遇到过一个问题:

假设您有一个1001整数的数组.整数是随机顺序,但您知道每个整数在1到1000之间(包括1和1000).此外,每个数字在数组中只出现一次,但一个数字除外,它出现两次.假设您只能访问数组的每个元素一次.描述一个算法来查找重复的数字.如果您在算法中使用了辅助存储,是否可以找到不需要它的算法？

我感兴趣的是第二部分,即不使用辅助存储.你有什么主意吗？

以下内容来自求职面试:

在包含整数的给定数组中,除了一个数字之外,每个数字重复一次,不重复.编写一个函数,查找不重复的数字.

我想过使用HashSet,但它可能会使一切变得复杂......

任何简单解决方案的想法？

埃森哲面试问题:

您已经获得了一个大小数组,2n+1其中包含n一对整数(可以是+ve,-ve或0)和一个不成对的元素.

你怎么会找到不成对的元素？

对意味着重复.所以(3,3)是一对和(3,-3)是不是一对.

可能重复:
在列表中查找单个数字

给定一组数字,除了一个数字,所有其他数字,出现两次.什么算法应该找到在数组中只出现一次的那个数字？

例

a[1..n] = [1,2,3,4,3,1,2] 

应该返回4

从查找列表中的单个数字扩展了该问题

如果我将问题扩展到这个问题:找到一个在列表中只出现一次的数字的最佳算法是什么？所有其他数字恰好出现k次？

有没有人有好的答案？

例如,A = {1,2,3,4,2,3,1,2,1,3},在这种情况下,k = 3.如何在O(n)中得到单个数字"4"时间和空间复杂度是O(1)？

因为这是一系列问题中的一个问题.我正在修改它以使其不与其他的重复.谢谢你的帮助.

对:我有一个整数数组.在数组中,除了一个元素外,每个元素都会出现两次.我想找到那个单号.

示例:[2, 4, 2, 1, 4, 1, 3],单个数字是3.

我的想法是使用a HashMap,这需要O(n)时间和O(n)空间.还有更好的解决方案吗？谢谢.

三元组:每个元素出现三次,除了一个.找一个单一的.

示例:[1, 2, 4, 2, 4, 1, 2, 4, 1, 3],单个数字是3.

我有一个数组,其中除了一个重复所有元素:

int[] a={2,6,6,2,4,1,4};

如何找到未配对的元素整数？

可能重复:
在列表中查找单个数字

给定一个整数数组的好算法,除了其中一个整数出现偶数次之外,找到一个出现奇数次的整数.

或许像二进制搜索一样的东西,比如2个n/2大小的小数组的所有元素,比较递归找出来？

编辑:

这个XOR算法实际上是假设{1,1,4,4,7,7,5,8,8,9,9}吗？我的输入也可以是randmon - {1,4,1,8,9,5,4,5,9,8}.那么这种情况下逻辑会发生变化吗？

您将获得一个包含正整数的数组.除了一个整数之外,所有整数都会出现偶数次.找到这个特殊的整数.

方案:

具有奇数出现次数的整数将具有0对或更多对以及一个单个数.所以,如果我们能够如何摆脱所有对,那么我们剩下的就是单个数字.什么摆脱对？提示:想想一个运营商.

异或会做到这一点.它为您提供O(n)解决方案,没有额外的内存.

int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];

for(int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}

数组中有许多数字,除了出现一次的一个特殊数字外,每个数字出现三次.这是一个问题:如何在数组中找到特殊数字？
现在我只能提出一些基数排序和快速排序的方法,这些方法无法利用问题的性质.所以我需要一些其他的算法.
谢谢你的帮助.

给定n个整数的列表,其中列表中的每个整数都存在两次,除了一个元素,它在列表中存在一次.例如,

[1 3 3 6 2 7 1 2 7]

我需要找到一个线性时间O(n)和一个常量空间O(1)算法,它返回列表中存在一次的元素.在上面的示例中,算法应返回6.请注意,列表不是由任何特定顺序提供的.(列表中元素的顺序是随机的).

我可以使用字典在O(n)线性时间内解决这个问题但不幸的是字典需要O(n)空间.有任何想法吗？