题目描述:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
限制:
1 <= 数组长度 <= 50000
解题思路:
- 摩尔投票法: 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1) ,为本题的最佳解法。
复杂度分析:
- 时间复杂度 O(N) : N 为数组
nums
长度。 - 空间复杂度 O(1):
votes
变量使用常数大小的额外空间。
class Solution{ public int majorityElement(int nums[]){ int vote=0,x=0;//vote:票数 x:众数 for(int num:nums){ if(vote==0) x=num; vote += (num==x)?1:-1;//当前数num等于众数x则vote+1,否则-1 } return x;//返回众数 } }
HashSet 类提供了很多有用的方法,添加元素可以使用 add() 方法:
// 引入 HashSet 类 import java.util.HashSet; public class RunoobTest { public static void main(String[] args) { HashSet<String> sites = new HashSet<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Zhihu"); sites.add("Runoob"); // 重复的元素不会被添加 System.out.println(sites); } }
结果:
[Google, Runoob, Zhihu, Taobao]
判断元素是否存在:
我们可以使用 contains() 方法来判断元素是否存在于集合当中:
// 引入 HashSet 类 import java.util.HashSet; public class RunoobTest { public static void main(String[] args) { HashSet<String> sites = new HashSet<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Zhihu"); sites.add("Runoob"); // 重复的元素不会被添加 System.out.println(sites.contains("Taobao")); } }
结果:
true
删除元素:
我们可以使用 remove() 方法来删除集合中的元素:
// 引入 HashSet 类 import java.util.HashSet; public class RunoobTest { public static void main(String[] args) { HashSet<String> sites = new HashSet<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Zhihu"); sites.add("Runoob"); // 重复的元素不会被添加 sites.remove("Taobao"); // 删除元素,删除成功返回 true,否则为 false System.out.println(sites); } }
结果:
[Google, Runoob, Zhihu]
删除集合中所有元素可以使用 clear 方法
计算大小
如果要计算 HashSet 中的元素数量可以使用 size() 方法:
// 引入 HashSet 类 import java.util.HashSet; public class RunoobTest { public static void main(String[] args) { HashSet<String> sites = new HashSet<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Zhihu"); sites.add("Runoob"); // 重复的元素不会被添加 System.out.println(sites.size()); } }
结果:
4
迭代 HashSet
可以使用 for-each 来迭代 HashSet 中的元素。
// 引入 HashSet 类 import java.util.HashSet; public class RunoobTest { public static void main(String[] args) { HashSet<String> sites = new HashSet<String>(); sites.add("Google"); sites.add("Runoob"); sites.add("Taobao"); sites.add("Zhihu"); sites.add("Runoob"); // 重复的元素不会被添加 for (String i : sites) { System.out.println(i); } } }
执行以上代码,输出结果如下:
Google Runoob Zhihu Taobao
添加元素
HashMap 类提供了很多有用的方法,添加键值对(key-value)可以使用 put() 方法:
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<Integer, String> Sites = new HashMap<Integer, String>(); // 添加键值对 Sites.put(1, "Google"); Sites.put(2, "Runoob"); Sites.put(3, "Taobao"); Sites.put(4, "Zhihu"); System.out.println(Sites); } }
执行以上代码,输出结果如下:
{1=Google, 2=Runoob, 3=Taobao, 4=Zhihu}
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<String, String> Sites = new HashMap<String, String>(); // 添加键值对 Sites.put("one", "Google"); Sites.put("two", "Runoob"); Sites.put("three", "Taobao"); Sites.put("four", "Zhihu"); System.out.println(Sites); } }
执行以上代码,输出结果如下:
{four=Zhihu, one=Google, two=Runoob, three=Taobao}
访问元素
我们可以使用 get(key) 方法来获取 key 对应的 value:
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<Integer, String> Sites = new HashMap<Integer, String>(); // 添加键值对 Sites.put(1, "Google"); Sites.put(2, "Runoob"); Sites.put(3, "Taobao"); Sites.put(4, "Zhihu"); System.out.println(Sites.get(3)); } }
执行以上代码,输出结果如下:
Taobao
删除元素
我们可以使用 remove(key) 方法来删除 key 对应的键值对(key-value):
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<Integer, String> Sites = new HashMap<Integer, String>(); // 添加键值对 Sites.put(1, "Google"); Sites.put(2, "Runoob"); Sites.put(3, "Taobao"); Sites.put(4, "Zhihu"); Sites.remove(4); System.out.println(Sites); } }
执行以上代码,输出结果如下:
{1=Google, 2=Runoob, 3=Taobao}
删除所有键值对(key-value)可以使用 clear 方法:
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<Integer, String> Sites = new HashMap<Integer, String>(); // 添加键值对 Sites.put(1, "Google"); Sites.put(2, "Runoob"); Sites.put(3, "Taobao"); Sites.put(4, "Zhihu"); Sites.clear(); System.out.println(Sites); } }
执行以上代码,输出结果如下:
{}
计算大小
如果要计算 HashMap 中的元素数量可以使用 size() 方法:
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<Integer, String> Sites = new HashMap<Integer, String>(); // 添加键值对 Sites.put(1, "Google"); Sites.put(2, "Runoob"); Sites.put(3, "Taobao"); Sites.put(4, "Zhihu"); System.out.println(Sites.size()); } }
执行以上代码,输出结果如下:
4
迭代 HashMap
可以使用 for-each 来迭代 HashMap 中的元素。
如果你只想获取 key,可以使用 keySet() 方法,然后可以通过 get(key) 获取对应的 value,如果你只想获取 value,可以使用 values() 方法。
// 引入 HashMap 类 import java.util.HashMap; public class RunoobTest { public static void main(String[] args) { // 创建 HashMap 对象 Sites HashMap<Integer, String> Sites = new HashMap<Integer, String>(); // 添加键值对 Sites.put(1, "Google"); Sites.put(2, "Runoob"); Sites.put(3, "Taobao"); Sites.put(4, "Zhihu"); // 输出 key 和 value for (Integer i : Sites.keySet()) { System.out.println("key: " + i + " value: " + Sites.get(i)); } // 返回所有 value 值 for(String value: Sites.values()) { // 输出每一个value System.out.print(value + ", "); } } }
执行以上代码,输出结果如下:
key: 1 value: Google key: 2 value: Runoob key: 3 value: Taobao key: 4 value: Zhihu Google, Runoob, Taobao, Zhihu,