平头哥的技术博文

平头哥的技术博文

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

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

双层 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;
}

我们借助一个临时变量来做这道题目,利用双层循环来统计一个自己相同个数的元素,因为是双层遍历,所以肯定有一个元素与自己相同,也就是元素自己本身。也就是说相同个数等于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;
}

这个实现摘抄自网上,平头哥是真心没看到,具体怎么实现的,咋也不知道为什么,咋也不敢问。

看完平头哥的实现,小伙伴们是不是有更好的实现方式呢?别藏着掖着了,在留言区里跟小伙伴们分享你的想法吧。

一题算法|找出只出现一次的数字-LMLPHP

08-23 00:38