百度集团网站建设方案,大学计算机网页设计教程,如何做网站拉动条,网站建设哪家最专业【问题描述】[数组中的重复数字][简单]
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0#xff5e;n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字重复了#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的…【问题描述】[数组中的重复数字][简单]
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。输入
[2, 3, 1, 0, 2, 5, 3]
输出2 或 3 【解答思路】
1. 排序后比较
时间复杂度O(NlogN) 空间复杂度O(1)
class Solution {public int findRepeatNumber(int[] nums) {Arrays.sort(nums);for(int i0;inums.length-1;i){if(nums[i]nums[i1]){return nums[i];}}return -1;}
}
2. HashSet
时间复杂度O(N) 空间复杂度O(N)
public int findDuplicate(int[] nums) {HashSetInteger set new HashSet();for (int i 0; i nums.length - 1; i) {if (set.contains(nums[i])) {return nums[i];}else{set.add(nums[i]);}}return -1;
}
3.原地置换 时间复杂度O(N) 空间复杂度O(1)
class Solution {public int findRepeatNumber(int[] nums) {int i 0;while(i nums.length) {if(nums[i] i) {i;continue;}if(nums[nums[i]] nums[i]) return nums[i];int tmp nums[i];nums[i] nums[tmp];nums[tmp] tmp;
//nums[nums[i]], nums[i] nums[i], nums[nums[i]]为什么这里的交换可以让元素的 索引 与 值 相等。//下面供大家方便看出来因为我看了好久才反应过来//记num[ i ] anum[num[ i ] ]num[ a ]b,那么 交换后num[ i ]b, num[num[i]]num[a]a这时候下标 a 对应的元素也是a达到目的}return -1;}
}
【总结】
1.考察的是程序员的沟通能力先问面试官要时间/空间需求
时间优先就用字典有空间要求就用指针原地排序数组要求空间O(1)并且不能修改原数组还得写成二分法
2.灵活思路 一题多解
3. HashMap 或 HashSet常见用法
3.1 HashSet
新建 HashSetInteger set new HashSet();1增加 public boolean add(E e); 2删除 public boolean remove(Object j); 3对比查找 public boolean contains(Object j); 4清空集合 public void clear(); 5获取长度 public int size(); 3.2 HashMap
新建 HashMapString,Integer map new HashMapString,Integer();1 插入键值对数据 public V put(K key, V value) 2根据键值获取键值对值数据 public V get(Object key) 3获取Map中键值对的个数 public int size() 4判断Map集合中是否包含键为key的键值对 public boolean containsKey(Object key) 5判断Map集合中是否包含值为value的键值对 boolean containsValue(Object value) 6判断Map集合中是否没有任何键值对 public boolean isEmpty() 7清空Map集合中所有的键值对 public void clear() 8根据键值删除Map中键值对 public V remove(Object key)
