安顺建设局网站,深圳网站设计工资一般多少,手机app游戏制作软件,网站开发怎样记录一下算法题的学习10
只出现一次的数字 leetcode题目#xff1a;给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题#xff0c;且… 记录一下算法题的学习10
只出现一次的数字 leetcode题目给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间 技巧 位运算 异或运算 Java中异或运算符^ 异或运算性质三种 任何数和0做异或运算结果仍然是原来的数即 a⊕0a。任何数和其自身做异或运算结果是 0即 a⊕a0。异或运算满足交换律和结合律即 a⊕b⊕ab⊕a⊕ab⊕(a⊕a)b⊕0b。 代码展示 class Solution {public int singleNumber(int[] nums) {int sole0;//遍历整个数组里的元素由于题目所给条件除了某个元素只出现一次以外其余每个元素均出现两次//合理使用异或运算的特点//我们最终获得的就是只出现一次的元素for(int num0;numnums.length;num){ sole^nums[num];}return sole;}
} 多数元素 leetcode题目给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。 1.摩尔投票法 核心理念为 票数正负抵消 候选人(candidates)初始化为 nums[0]票数 count 初始化为 1。当遇到与candidates 相同的数则票数 count count 1否则票数 count count - 1。当票数 count 为 0 时更换候选人并将票数 count 重置为 1。遍历完数组后candidates 即为最终答案
class Solution {public int majorityElement(int[] nums) {int candidates nums[0], count 1;for (int i 1; i nums.length; i) {if (candidates nums[i])count1;else if ( --count 0) {candidates nums[i];count 1;}}return candidates;}
} 2.数组排序法 将数组 nums 排序数组中点的元素 一定为众数。代码展示 class Solution {public int majorityElement(int[] nums) {//数组升序Arrays.sort(nums);int most_number0; //初始化多数元素--》众数为0most_numbernums[nums.length/2]; //将数组 nums 排序数组中点的元素 一定为众数。return most_number;}
}
class Solution {public int majorityElement(int[] nums) {//数组降序 jdk8使用Integer[] integers Arrays.stream(nums).boxed().toArray(Integer[]::new);Arrays.sort(integers ,Collections.reverseOrder ());int most_number0; //初始化多数元素--》众数为0most_numberintegers[integers.length/2]; //将数组 nums 排序数组中点的元素 一定为众数。return most_number;}
} 注意 如果想要使用降序Arrays.sort(scores,Collections.reverseOrder());。首先要注意的是不能用int这个类型了要用Integer不能使用基本类型int,double, char如果是int型需要改成Integerfloat要改成Float 举例Integer[] 和int[] 互转 jdk8使用Stream流来实现互相转化 // int[] -- Integer[]
int[] arr {1, 2, 3, 4, 5};
Integer[] integers Arrays.stream(nums).boxed().toArray(Integer[]::new);
// Integer[] -- int[]
int[] nums Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();3.哈希表统计法 遍历数组 nums 用 HashMap 统计各数字的数量即可找出众数 方法作用getOrDefault() 获取指定 key 对应对 value如果找不到 key 则返回设置的默认值 hashmap.getOrDefault(Object key, V defaultValue) Map.EntryMap声明的一个内部接口此接口为泛型定义为EntryK,V。它表示Map中的一个实体一个key-value对。接口中有getKey(),getValue方法。map.entrySet() java中 键-值 对的集合Set里面的类型是Map.Entry一般可以通过map.entrySet()得到。 entrySet实现了Set接口里面存放的是键值对。一个K对应一个V
class Solution {public int majorityElement(int[] nums) {HashMapInteger,Integer mapnew HashMap();//建立一个哈希表for(int i0;inums.length;i){map.put(nums[i],map.getOrDefault(nums[i],0)1);//将nums集合里面的元素添加到哈希表中}int key 0;int value 0;//哈希表遍历找到众数for(Map.EntryInteger,Integer entry:map.entrySet()){if(entry.getValue()value){value entry.getValue();key entry.getKey();}}return key;}
} 结束拜拜
