seo网站推广案例,公关公司服务的特点,济南哪家做网站,中国移动视频网站建设java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 解题思路 子序列要尽可能长#xff0c;并且最大值和最小值之间的差#…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 解题思路 子序列要尽可能长并且最大值和最小值之间的差必须为1。所以这道题的迷惑点在于最大值最小值之间可以插入任意个数的元素。但是只要我们把数字列出来2,2,2,3,3,3,你会发现根本不能插入任何其它数字例如2,2,2,1,3,3,3, 此时的差可不是1而是3-12了。因此这道题可以理解为找数组中两个数相差为1并且两个元素的出现次数相加为最多。法一hash表时间复杂度O(n),空间复杂度O(n). 可以使用hash表记录每个元素的出现次数如果两个元素相差为1就记录它们的出现次数最终返回最大的出现次数。法二排序双指针时间复杂度O( n ∗ l o g 2 N n*log_2{N} n∗log2N),空间复杂度O(1). 先对数组排序然后left指针指向前一个元素right指针指向后一个元素如果相差为1记录它们的长度 代码 法一hash表 class Solution {public int findLHS(int[] nums) {//hashMap表key当前元素值value出现次数MapInteger,Integer map new HashMap();int res 0;//最多的出现次数//遍历数组如果当前元素第一次遇到直接放入map中次数置为1//如果不是第一次遇到获取它已经出现的次数1for(int num:nums) map.put(num,map.getOrDefault(num,0)1);//遍历key值寻找每个key在map中是否存在比它大1的key如果存在那么他俩可以组成一个子序列//他俩各自的出现次数就是子序列的长度for(int key:map.keySet()){//如果找到了那么我们只保存最大的子序列长度if(map.containsKey(key 1)) res Math.max(res,map.get(key)map.get(key1));}return res;}
}法二排序双指针排序使用快速排序时间复杂度O( n ∗ l o g 2 n n*log_2{n} n∗log2n),双指针遍历两遍数组时间复杂度O(2N), 最终时间复杂度O( n ∗ l o g 2 n n*log_2{n} n∗log2n)空间复杂度O(1)。 class Solution {public int findLHS(int[] nums) {Arrays.sort(nums);//先对数组排序O(N*log2N)int left 0, right 0;//双指针指向两个相邻的值不同的元素int cnt 0, max 0;//while(right nums.length){//右指针不能越界//如果left指向的元素和right指向的元素的差 1,left后移while(nums[left] 1 nums[right]) left;//如果left和right所指元素的差正好差1说明这两个数组成的序列满足条件if(nums[right] nums[left] 1){//right所指向的元素的后面如果是重复的值right右移,直到不重复为止while(rightnums.length nums[right] nums[left] 1) right;right--;//前移一个就是最后一个重复的值cnt right - left 1;//计算子序列长度max Math.max(max, cnt);//只保留较大的子序列长度}right;//右指针不断后移}return max;}
}
