data-structures - 在 O(n) 中找到没有 XOR 或 Map 的给定数组中的 1 个非重复元素

Question

当我不允许使用哈希映射或运算符XOR时，如何在数组中找到所有其他元素恰好出现两次的一个非重复元素？

在 O(n) 时间复杂度

例子：

输入

arr[] = {14, 1, 14, 4, 12, 2, 1, 2, 3, 3}

输出

4

标签： data-structures

Answer 1

如果您想在 java Script 中执行此操作，那么在 for 循环中您可以检查该项目的第一个索引和最后一个索引是否相同，然后返回该项目，否则返回 -1。

function getFirstDistinctNumber() {
  arr = [14, 1, 14, 4, 12, 2, 1, 2, 3, 3];

  for (let i=0; i<arr.length; i++) {
    if(arr.indexOf(arr[i]) == arr.lastIndexOf(arr[i])) {
      return arr[i];
    }
  }
  return -1;
}

console.log(getFirstDistinctNumber());

而且在java中，你也可以做同样的事情，但lastIndexOf()数组不存在。所以你可以通过创建一个数组列表来做到这一点

import java.util.*;

class FindDistinct {
   public static void main(String[] args) {
   // create an empty array list with an initial capacity
   ArrayList<Integer> inputList = new ArrayList<Integer>();
   // use add() method to add values in the list
   inputList.add(14);
   inputList.add(1);
   inputList.add(14);
   inputList.add(4);
   inputList.add(12);
   inputList.add(2);
   inputList.add(1);
   inputList.add(2);
   inputList.add(3);
   inputList.add(3);

   for(int i=0; i< inputList.size(); i++) {
     if(inputList.indexOf(inputList.get(i)) == inputList.lastIndexOf(inputList.get(i))) {
        System.out.println(inputList.get(i));
        break;
     }
   }
 }
}