算法面试：数组编码面试问题

栏目: 编程工具 · 发布时间: 6年前

内容简介：数组是最基本的数据结构，它将元素存储在连续的内存位置。这也是面试官最喜欢的话题之一，在任何编码面试中，你都会听到很多关于数组的问题，例如，颠倒数组、排序数组或搜索数组中的元素。数组数据结构的主要优点是，如果知道索引，它可以提供快速的0（1）搜索，但是从数组中添加和删除元素的速度很慢，因为一旦创建了数组，就无法更改其大小。要创建更短或更长的数组，您需要创建一个新数组并将所有元素从旧复制到新的。

数组是最基本的数据结构，它将元素存储在连续的内存位置。这也是面试官最喜欢的话题之一，在任何编码面试中，你都会听到很多关于数组的问题，例如，颠倒数组、排序数组或搜索数组中的元素。

数组数据结构的主要优点是，如果知道索引，它可以提供快速的0（1）搜索，但是从数组中添加和删除元素的速度很慢，因为一旦创建了数组，就无法更改其大小。

要创建更短或更长的数组，您需要创建一个新数组并将所有元素从旧复制到新的。

解决基于数组的问题的关键是熟悉数组数据结构以及基本编程构造函数，如循环，递归和基本运算符。

问题：

在给定的1到100的整数数组中，如何查找缺少的数字？

有关编程访谈的最常见问题之一是，编写一个程序，用Java，C＃或任何其他语言查找数组中缺少的数字。这种编码面试问题不仅在小型初创企业中被问到，而且还在谷歌，亚马逊，Facebook，微软等一些最大的技术公司中提出，主要是当他们访问知名大学的校园招聘毕业生时。这个问题的最简单版本是在100个整数的区域中找到缺失的元素，其中包含1到100之间的数字。这可以通过使用n（n + 1）/ 2计算序列的总和来轻松解决，这是也是最快捷有效的方法之一，但如果数组包含多个缺失的数字或者数组包含重复项，则无法使用它。

这给了面试官一些很好的后续问题，以检查候选人是否可以应用他对略有不同的条件的知识。因此，如果您完成此操作，他们会要求您在重复数组中找到缺少的数字。这可能很棘手但你很快就会发现在数组中找到缺失和重复数字的另一种方法是对它进行排序。

在排序数组中，您可以比较数字是否等于预期的下一个数字。或者，您也可以使用 Java 中的BitSet来解决此问题。

如何使用Java程序找到缺少的数字

首先理解问题陈述，我们将1到100的数字放入整数数组中，找出丢失的数字的最佳方法是什么？如果访问者特别提到1到100，那么你可以应用上述关于系列总和的技巧，如下所示。如果它有多个缺少的元素，你可以使用BitSet类，当然只有你的面试官允许它。

1）系列之和：公式：n（n + 1）/ 2（但只适用于一个缺失的数字）

2）如果数组有多个缺少的元素，请使用BitSet。

BitSet解决方案，是很好的实用程序类。在许多面试中，当向Java开发人员询问时，他们中的许多人甚至都没有意识到这一点。这个问题是学习如何在Java中使用BitSet的好方法。

如果你要去面试，那么除了这个问题之外，最好还要知道如何在数组和程序中找到重复数字以及找到整数数组中的第二高数字。通常情况下，这些问题会作为后续问题出现。

<b>import</b> java.util.Arrays;
<b>import</b> java.util.BitSet;
 <font><i>/** 
* Java program to find missing elements in a Integer array containing 
  * numbers from 1 to 100. 
* 
* @author Javin Paul 
*/</i></font><font>
<b>public</b> <b>class</b> MissingNumberInArray {
 
     <b>public</b> <b>static</b> <b>void</b> main(String args[]) {

        </font><font><i>// one missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 6}, 6);
 
        </font><font><i>// two missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
 
        </font><font><i>// three missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 6, 9, 8}, 10);
 
        </font><font><i>// four missing number</i></font><font>
        pr<b>int</b>MissingNumber(<b>new</b> <b>int</b>[]{1, 2, 3, 4, 9, 8}, 10);
 
        </font><font><i>// Only one missing number in array</i></font><font>
        <b>int</b>[] iArray = <b>new</b> <b>int</b>[]{1, 2, 3, 5};
        <b>int</b> missing = getMissingNumber(iArray, 5);
        System.out.printf(</font><font>"Missing number in array %s is %d %n"</font><font>, 
                           Arrays.toString(iArray), missing);
    }
   </font><font><i>/**    
* A general method to find missing values from an integer array in Java.    
* This method will work even if array has more than one missing element.
*/</i></font><font>
    <b>private</b> <b>static</b> <b>void</b> pr<b>int</b>MissingNumber(<b>int</b>[] numbers, <b>int</b> count) {
        <b>int</b> missingCount = count - numbers.length;
        BitSet bitSet = <b>new</b> BitSet(count);
 
        <b>for</b> (<b>int</b> number : numbers) {
            bitSet.set(number - 1);
        }
 
        System.out.printf(</font><font>"Missing numbers in integer array %s, with total number %d is %n"</font><font>,
        Arrays.toString(numbers), count);
        <b>int</b> lastMissingIndex = 0;

        <b>for</b> (<b>int</b> i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
 
    }
   </font><font><i>/**    
* 在数组中查找缺失数的 java方法
* 仅1到n之间的数字.    
* 可用于查找整数数组中缺少的元素
*数字从1到100或1-1000    
*/</i></font><font>
    <b>private</b> <b>static</b> <b>int</b> getMissingNumber(<b>int</b>[] numbers, <b>int</b> totalCount) {
        <b>int</b> expectedSum = totalCount * ((totalCount + 1) / 2);
        <b>int</b> actualSum = 0;
        <b>for</b> (<b>int</b> i : numbers) {
            actualSum += i;
        }
 
        <b>return</b> expectedSum - actualSum;
    }
 
}
</font>

输出：

Missing numbers in integer array [1, 2, 3, 4, 6], with total number 6 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 7, 9, 8, 10], with total number 10 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 9, 8], with total number 10 is
5
7
10
Missing numbers in integer array [1, 2, 3, 4, 9, 8], with total number 10 is
5
6
7
10
Missing number in array [1, 2, 3, 5] is 4

您可以看到，使用正确的数据结构如何轻松解决问题，这是这个程序的关键收获，了解这个技巧是很好的，它只需要计算数字的和，然后从实际的和中减去它，但是如果数组中缺少一个以上的数字，就不能使用这个技巧。另一方面，位集Bitset解决方案更通用，因为您可以使用它在整数数组中查找多个缺少的值。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

TCP/IP网络管理

亨特 / 电子工业 / 2006年3月1日 / 79.00元

本书是一本架设与维护TCP／IP网络的完整指南，无论你是在职的系统管理员，还是需要访问Internet的家用系统用户，都可从本书获得帮助。本书还讨论了高级路由协议(RIPv2、OSPF、BGP)，以及实现这些协议的gated软件。对于各种重要的网络服务，如DNS，Apache，sendmail，Samba，PPP和DHCP，本书都提供了配置范例，以及相关的软件包与工具的语法参考。一起来看看《TCP/IP网络管理》这本书的介绍吧!

码农工具

JSON 在线解析

在线 JSON 格式化工具

HEX CMYK 转换工具

HEX CMYK 互转工具