在一个数组中找到一个单独的整数

Question

我正在尝试解决一个算法问题。我需要在一个数组中找到一个单独的整数。

例如： {1,1,5,5,5,3,2,2}

输出应该是3，因为那是唯一的单个整数。

到目前为止，我创建了一个算法，首先对数组进行排序，然后检查i-1和i+1元素是否相等，如果不相等，则意味着我已经找到了单独的整数。

问题在于：对于短输入，它工作得很好，但是对于长输入，我会接收超时错误（计算时间太长，因此我的答案未经验证）。

您能否给我任何改进算法的提示？

static int lonelyinteger(int[] a) {

    Arrays.sort(a);

    if (a.length == 1)
        return a[0];

    for (int i = 0; i < a.length; ++i) {

        if (i == 0) {
            if (a[i + 1] != a[i])
                return a[i];
        } else if (i == a.length - 1) {
            if (a[i] != a[i - 1])
                return a[i];
        } else {
            if (a[i - 1] != a[i] && a[i + 1] != a[i])
                return a[i];
        }  
    }
    return -1;
}

- waff

---

请给出一个导致此情况发生的输入示例。 - tnw

你不需要对数组进行排序。只需遍历一次，构建一个映射表，记录每个数字及其出现的次数。然后只需打印计数器等于1的数字即可。 - Traveling Tech Guy

什么是“超时”？ - SamTebbs33

地图的想法有效，但请记住相比于原地排序，它需要大约三倍的内存（这取决于单个和多个条目的数量）。对于小的N值来说这并不重要，但是对于非常大的N值相对可用内存来说就很重要了。 - Eric J.

你需要识别所有“单例”整数（如果存在多个），还是只需要第一个？或者我们假设只有一个存在？ - David W

Answer 1

你确定你理解了问题吗？孤独整数算法问题的想法是，除了一个数字外，所有数字都成对出现。从你使用的示例来看，情况并非如此。

如果所有数字都成对出现，除了一个数字，找到解决方案的最快方法是对所有元素应用异或。由于在两个相同元素之间应用异或会将它们取消，因此您将得到您正在寻找的孤独整数。此解决方案的时间复杂度为O(n)。

否则，如果给定数组中可以找到一个数字超过两次，或者您使用提供的解决方案，则时间复杂度为O(n*logn)。

- Stanislav

---

问题是正确的。我只是想问是否有任何方法可以改进解决方案，使其比现在更快地工作。 - waff

对于那种情况，很抱歉给您带来了误导。 - Stanislav

Answer 2

这个问题不认为O(N^2)速度足够快吗？

我有一个包含随机成对值的1千万元素列表。在随机位置上，我放置了“孤独的整数”5，并且O(N^2)可以快速解决它而无需排序。该算法在找到第一个“孤独的整数”时停止。

public static void main(String[] args) {
    Random r = new Random();

    List<Integer> ints = new ArrayList<>();
    for (int i = 0; i < 10000000; i += 2) {
        int randomNumber = r.nextInt(100) + 10;
        ints.add(randomNumber);
        ints.add(randomNumber);
    }
    ints.add(5); // Lonely Integer

    int tempIndex = r.nextInt(ints.size());
    int tempValue = ints.get(tempIndex);
    // Swap duplicate integer with lonely integer
    ints.set(tempIndex, ints.get(ints.size() - 1)); 
    ints.set(ints.size() - 1, tempValue);

    for (int i = 0; i < ints.size(); i++) {
        boolean singleInteger = true;
        for (int j = 0; j < ints.size(); j++) {
            if (j == i) {
                continue;
            }
            if (ints.get(j) == ints.get(i)) {
                singleInteger = false;
                break;
            }
        }

        if (singleInteger) {
            System.out.println("Single instance: " + ints.get(i));
            break;
        }
    }
}

结果:

单个实例: 5 (约10-20秒);

更新

您的方法约3秒。

地图解决方案...

public static void main(String[] args) {
    Random r = new Random();

    List<Integer> ints = new ArrayList<>();
    for (int i = 0; i < 10000000; i += 2) {
        int randomNumber = r.nextInt(100) + 10;
        ints.add(randomNumber);
        ints.add(randomNumber);
    }
    ints.add(5); // Lonely Integer
    int tempIndex = r.nextInt(ints.size());
    int tempValue = ints.get(tempIndex);
    // Swap duplicate integer with lonely integer
    ints.set(tempIndex, ints.get(ints.size() - 1));
    ints.set(ints.size() - 1, tempValue);

    Map<Integer, Integer> counts = new HashMap<>();
    for (int i : ints) {
        if (counts.containsKey(i)) {
            counts.put(i, counts.get(i) + 1);
        } else {
            counts.put(i, 1);
        }
    }

    for (Integer key : counts.keySet()) {
        if (counts.get(key) == 1) {
            System.out.println("Single Instance: " + key);
        }
    }
}

结果：

单个实例：5（约1-3秒）

- Shar1er80

---

@sodium24 是的...我撤回了我的更新，因为我发现多个“孤独整数”，在随机数字对和所有相同数字之间进行比较后。之后，我想确保在随机数字对中找到第一个“孤独整数”仍然有效，结果是有效的。 - Shar1er80

抱歉问一个新手问题，我正在学习算法，但我不太明白如何计算时间复杂度。但是，我认为我的当前解决方案具有O(n*logn)的复杂度，难道O(N^2)不比它更糟糕吗？ - waff

Arrays.sort是一种快速排序方法，平均时间复杂度为O(n log(n))。这是谷歌所说的，但我并不是专家。可以查看http://bigocheatsheet.com/和https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(byte[])。 - waff

@waff 是的，我也读过那个，但是在 O(N * logN) 排序之后又进行了一次 O(n) 的搜索。这两者结合起来仍然比 O(n^2) 更快吗？我仍在学习 O 表示法。 - Shar1er80

@waff 你说得对，O(N*logN) + O(N) 的搜索仍然比 O(N^2) 好得多。我尝试了 Map 方法，看起来速度更快。请查看更新... - Shar1er80

Answer 3

首先检查是否由于输入数据过大导致Arrays.sort(a);运行时间过长。

如果不是这种情况，您可以按照以下方法改进您的方法：

 static int lonelyinteger(int[] a) {
    if (a[0] != a[1]) return a[0];

    int i = 1;
    while ((i < a.length - 1) && (a[i] == a[i-1] || a[i] == a[i+1])) {
        i++;
    }

    if ((i < a.length -1) || (a[i] != a[i-1]))  return a[i];
    return -1;
}

- Jihed Amine

Answer 4

排序。然后...

while (true) {
    if (a[0] != a[1]) {
        return a[i].
  } else {
      remove all a[0]s from a.
  }
}

这是O(nlogn)。

找到所有唯一整数的O(n)解决方案（不需要排序）是使用哈希表并沿着数组运行。如果数字未出现在哈希表中，则将该数字添加到哈希表中。如果数字已经出现在哈希表中，则从哈希表中删除该数字。最后，您将在一个哈希表中拥有所有唯一的整数。妙啊。

- marcomarandiz