在一个数组中查找未配对的数字

Question

在一个数组中查找未配对的数字

7

我有一个数组，除了一个元素外，所有元素都重复了:

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

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

- Anuj Balan

1

请在您的问题中发布该代码。 - Jeffrey

发布你所做的事情，社区会在出现问题时提供帮助。 - kosa

1

可能是重复的问题，与Accenture面试题 - 在数组中找到唯一的未配对元素相同。 - Roland Illig

可能是在列表中查找单个数字的重复问题。 - outis

可能是重复的问题，与Accenture面试题 - 在数组中找到唯一的未配对元素相似。 - Iłya Bursov

显示剩余3条评论

3个回答

2

你可以使用一个映射来记录数字出现的次数。虽然可能有更好的方法，但这种方法是可行的。

public static void main( String[] args ) {
    int[] a = { 2, 6, 6, 2, 4, 1, 4 };

    Map<String, Integer> counts = new HashMap<String,Integer>();

    String key;
    for ( int i : a ) {
        key = String.valueOf( i );
        if ( counts.containsKey( key ) ) {
            int count = counts.get( key );
            counts.put( key, ++count );
        }
        else {
            counts.put( key, 1 );
        }
    }

    for ( Map.Entry<String, Integer> entry : counts.entrySet() ) {
        if ( entry.getValue() < 2 ) {
            System.out.println( entry.getKey() + " does not have a pair" );
        }
    }
}

- chooban

在他给我的一分钟时间内，我无法想出这样的解决方案。 :( - Anuj Balan

3

不需要把int转换成String，只需要使用Map<Integer,Integer>就可以了。 =) - Demetrio Neto

0

在Codility示例中列出了一个例子，我在那里测试了这个代码，并发现对于某些测试用例存在一些不正确性和性能问题。

- ammad

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

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

- ruakh · Accepted Answer

有几种方法可以解决：

1. O(n log n)的方法：对数组进行排序，然后迭代排序后的数组中的元素，每次迭代取两个元素(i=0, i=2等)。当a[i]和a[i+1]不相等或者i+1等于a.length时，就知道a[i]没有成对出现。

2. O(n^2)的方法：迭代数组中的元素，在嵌套循环中对每个元素a[i]进行迭代并查看是否存在a[i]==a[j]且i!=j的情况。如果不存在这种情况，则a[i]没有成对出现。

3. O(m)的方法，其中m是最大元素和最小元素之间的差（注意到m是Ω(n)的）：迭代元素，找到最大值和最小值MIN和MAX。创建一个int[] b = new int[MAX-MIN+1]。再次迭代元素，为每个元素递增b[a[i]-MIN]。然后迭代b；当你发现b[j]==1时，j就是没有成对出现的元素。

注意：您使用了"element integer"这一术语，但这不是一个真正的术语。以上假定您的意思是“整数值元素”。如果您的实际意思是“元素索引”，则只有在修改Approach 3时才能使用Approach 2。需要对Approach 3进行一些调整，Approach 1需要进行大量的调整。（当然，一旦找到了只出现一次的值，您可以再次迭代数组以找到该值的索引-前提是您仍然拥有原始数组顺序）。

编辑后添加：我不知道为什么之前错过了这一点——我猜写Java时没有习惯位运算——但最好的解决方案实际上是：

4. O(n)的方法：计算数组所有元素的按位异或^。这就是没有成对出现的元素。因为XOR是可交换和可结合的，所以2^6^6^2^4^1^4等于1^(2^2)^(4^4)^(6^6)，而x^x永远是0，所以成对出现的元素会相互抵消。你可以像下面那样编写代码：

int result = 0;
for(int i : a)
    result ^= i;

计算未配对的元素。（为了获取未配对元素的索引，你需要再次遍历数组，查找result。）