【LeetCode】12 只出现一次的数字 II

题目:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

思路:

image.png

代码:

遍历输入数组,统计每个数字出现的次数,最后返回出现次数为 1 的数字。

class Solution {
  public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> hashmap = new HashMap<>();
    for (int num : nums)
      hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);

    for (int k : hashmap.keySet())
      if (hashmap.get(k) == 1) return k;
    return -1;
  }
}

复杂度分析

时间复杂度:O(N),遍历输入数组。

空间复杂度:O(N),存储 N/3 个元素的 Set。

用到的一些需要记住的知识点:

①hashmap.getOrDefault(key,defaultValue):

HashMap类实现的Map接口的**getOrDefault(Object key,V defaultValue)**方法用于获取使用指定键映射的值。如果没有使用提供的键映射任何值,则返回默认值。

句法:

默认V getOrDefault(对象键,V defaultValue)

**参数:**此方法接受两个参数:

  • key:这是必须获取其值的元素的

  • defaultValue:如果未使用指定的键映射任何值,则必须返回的默认值

返回值:该方法返回的值与指定键映射,否则默认值返回。

image.png

②hashmap.getOrDefault(key,defaultValue):

HashMap类实现的Map接口的**getOrDefault(Object key,V defaultValue)**方法用于获取使用指定键映射的值。如果没有使用提供的键映射任何值,则返回默认值。

句法:

默认V getOrDefault(对象键,V defaultValue)

**参数:**此方法接受两个参数:

  • key:这是必须获取其值的元素的
  • defaultValue:如果未使用指定的键映射任何值,则必须返回的默认值

返回值:该方法返回的值与指定键映射,否则默认值返回。

image.png

③Java 增强 for 循环

Java5 引入了一种主要用于数组的增强型 for 循环。

Java 增强 for 循环语法格式如下:

for(声明语句 : 表达式) {
//代码句子 
}

**声明语句:**声明新的局部变量,该变量的类型必须和数组元素的类型匹配。其作用域限定在循环语句块,其值与此时数组元素的值相等。

**表达式:**表达式是要访问的数组名,或者是返回值为数组的方法。

实例

public class Test {
   public static void main(String args[]){
      int [] numbers = {10, 20, 30, 40, 50};
 
      for(int x : numbers ){
         System.out.print( x );
         System.out.print(",");
      }
      System.out.print("\n");
      String [] names ={"James", "Larry", "Tom", "Lacy"};
      for( String name : names ) {
         System.out.print( name );
         System.out.print(",");
      }
   }
}

以上实例编译运行结果如下:

10,20,30,40,50,
James,Larry,Tom,Lacy,

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×