数据结构算法题总汇
2021/10/25 11:10:13
本文主要是介绍数据结构算法题总汇,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2021年10月25日数组练习
题目一:leetcode136.只出现一次的数字
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解思路:
1.拿到题目后第一反应是借助一个hash表来进行记录,但是空间复杂度会变为O(n),不符合题意。代码如下:
public int singleNumber(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])){ map.put(nums[i],map.get(nums[i])+1); }else{ map.put(nums[i],1); } } for (Integer integer : map.keySet()) { int count = map.get(integer); if (count == 1){ return integer; } } return -1; }
2.由于上一个解法使用hash导致空间复杂度提高,所以随后想到使用排序算法进行解题,但是使用快排的时间复杂度也达到了O(nlogn),所以放弃。
public int singleNumber(int[] nums) { Arrays.sort(nums); int result = 0; if(nums.length == 1){ return nums[0]; } if (nums[0] != nums[1]){ return nums[0]; } for (int i = 1; i < nums.length; i++) { if (i== nums.length-1){ if (nums[nums.length-1] != nums[nums.length-2]){ return nums[nums.length-1]; } break; } if (nums[i] == nums[i+1] || nums[i-1] == nums[i]){ }else{ result = nums[i]; } } return result; }
3.由于本人能力不足,想到这里就到头了,所以就默默的打开了题解,看到了一种异或操作来解这题,异或操作是属于相同为0,不同为1的运算,所以刚好用来解这题。
public int singleNumber(int[] nums) { int result = nums[0]; if (nums.length > 1){ for (int i = 1; i < nums.length ; i++) { result = result ^ nums[i]; } } return result; }
4.还有一种解法,暴力解法,这个解法就不做解释了,就是将一个元素拿出来对数组剩下的元素做对比,时间复杂度达到了O(n平方)。
这篇关于数据结构算法题总汇的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求