数组找出只出现了一次的元素

待我称王封你为后i 2024-04-17 05:40 64阅读 0赞

题算法｜找出只出现一次的数字

#### 题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次，找出那个只出现了一次的元素。(leetcode-136题) ####

这道算法题在leetcode的难度为简单，这道题看上去跟去重差不多意思，就是将不重复的找出来，平头哥首先想到的是简单粗暴的双层循环来解决这个问题，没办法就是这样记几控制不住记几，使用洪荒之力控制住记几后，还想出来了两种办法来解决这个问题，利用 map 、list的特性来解决。网上果然是卧虎藏龙的地方，想出了用异或运算符来解决，来讲讲自己的思路吧。

###### 双层 for 循环实现 ######

/** * 双层for循环 * * @param nums * @return */
    public static Integer forSoution(int[] nums) { 
      for (int i = 0; i < nums.length; i++) { 
          //相同个数
          int equalCount = 0;
          for (int j = 0; j < nums.length; j++) { 
              if (nums[i] == nums[j]) { 
                  equalCount += 1;
              }
          }
          // 除本身外没有其他相同的数字了
          if (equalCount == 1)
              return nums[i];
      }
    
      return -1;
    }

我们借助一个临时变量来做这道题目，利用双层循环来统计一个自己相同个数的元素，因为是双层遍历，所以肯定有一个元素与自己相同，也就是元素自己本身。也就是说相同个数等于１就是没有相同的元素，即该元素就出现了一次。这样我们就找出来了只出现一次的元素。

##### 利用 list 实现 #####

/** * list * * @param nums * @return */
    public static Integer listSolution(int[] nums) { 
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) { 
            // 利用list删除返回true的特性
            if (!list.remove(Integer.valueOf(nums[i]))) { 
                list.add(Integer.valueOf(nums[i]));
            }
        }
        if (list.size() == 1) { 
            return list.get(0);
        }
        return -1;
    }

因为list.remove()方法返回值为true，所以我们可以利用这个特性来解决这个问题。我们先实例化一个空的list集合，在遍历数组时，我们先调用list.remove()方法来删除该值。如果删除成功，说明该值已经重复了。如果删除不成功，就说明在list中没有找到，则我们将该值添加到list里，将所有元素遍历完之后，留在list里面的就是只出现了一次的元素。

##### 利用Map实现 #####

/** * 利用 hashmap 实现 * * @param nums * @return */
    public static Integer mapSolution(int[] nums) { 
        Map<Integer, Object> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) { 
            // 将值作为　map 的key，如果map包含该key就删除该key
            if (map.containsKey(nums[i])) { 
                map.remove(nums[i]);
            } else { 
                map.put(nums[i], 1);
            }
        }
        if (map.keySet().size() == 0 || map.keySet().size() > 1) { 
            return -1;
        }
        return map.keySet().iterator().next();
    }

map提供了一个containsKey()方法来判断传入的key是否存在map中，利用这个特性也能解决这个问题。我们先实例化一个空的HashMap，遍历数组，判断数组的值是否作为key存在map中，如果存在，则将这个key移除，如果不存在，则将这个值作为key添加到map中，map的值随意。遍历完之后，map中的key就是只出现了一次的元素。

##### 利用异或运算实现 #####

/** * 摘抄自网上，没看懂 异或运算 * * @param nums * @return */
    public static Integer xorSolution(int[] nums) { 
       int ans = nums[0];
       if (nums.length > 1) { 
           for (int i = 1; i < nums.length; i++) { 
               ans = ans ^ nums[i];
           }
       }
       return ans;
    }

这个实现摘抄自网上。