package com.ko.leetcode.primaryAlgorithm.array;
/**
* 《初级算法》
* -数组
* 1.删除排序数组中的重复项
* @Author ko
* @Date 2023/6/1 23:55
* @Version 1.0
*/
public class removeDuplicatesSolution {
/*给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2gy9m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
//系统会用下面的代码来测试你的题解:
public static void main(String[] args) {
/*int[] nums = new int[]{1,1,2,2,3,3,4,5,6,6,7};*/// 输入数组
/*int[]nums = new int[]{0,0,1,1,1,2,2,3,3,4};*/
int[]nums = new int[]{1,1};
/*int[] expectedNums = new int[]{1,2,3,4,5,6,7};*/ // 长度正确的期望答案
/*int[] expectedNums = new int[]{0,1,2,3,4};*/
int[] expectedNums = new int[]{1};
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
}
/**
* 第一次通过
* 执行用时：
* 354 ms
* , 在所有 Java 提交中击败了
* 5.26%
* 的用户
* 内存消耗：
* 42.6 MB
* , 在所有 Java 提交中击败了
* 98.29%
* 的用户
* 通过测试用例：
* 361 / 361
* @author keyi
* @Date 2023/6/2 1:38
* @param
* @return
*/
public static int removeDuplicates(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
int length = nums.length;
for(int i=0;i<=length-2;i++){
int j=i+1;
while (j<length&&nums[i]==nums[j]){
for(int k=j;k<length-1;k++){
nums[k]=nums[k+1];
}
//找出一个重复的
length--;
}
//因为nums是升序的，所以后面那个数如果大于前面那个数就结束这个循环
if(nums[j]>nums[i]){
continue;
}
}
return length;
}
}
一.第一次可以运行的代码
时间复杂度 O（n的2次方）
空间复杂度 O(1)
二.需要注意的问题
1.需要排除异常情况、空指针
2.数组下标越界问题 注意数组的边界
三.leetcode官方题解及我的笔记
暴力解法:如果可以使用额外的空间，就直接把不重复的元素复制到新的的数组里。时间复杂度：O(n） 空间复杂度：O(n)
1.双指针
原地修改 模式识别
官方解法和我第一次解法的区别：官方是用到两个指针，慢指针，快指针，而我的解法用到了双层的循环，所以时间复杂度是0（n的2次方）。我的思路是从数组第一个也就是nums[0]开始遍历，从前往后找，而官方题解的思想是从第二个开始，从后往前（同时指针往后移动）。我的解法是遇到重复的就进行覆盖的操作，而官方题解巧妙之处在于是，遇到不重复的再操作
双指针中的“指针” 不仅仅是大家所熟知的C/C++里面的地址指针，还是索引、游标。
四.双指针算法的业务场景
（来自gpt）
- 在一个日志文件中查找某个时间段内的数据（其实就是起始与结束的时间作为两个指针）
- 给定两个有序数组，查找它们的交集或并集（具体思路是，定义两个指针分别指向两个数组的开头，然后比较两个指针所指向的元素大小，并根据大小关系移动指针。如果两个指针所指向的元素相同，则将其添加到结果集中。）
- 在一个升序排列的链表中查找倒数第k个节点（具体思路是，定义两个指针
p和q，初始时都指向链表的头结点，并将其中一个指针向后移动k-1步，然后同时移动两个指针，直到第二个指针达到链表末尾位置。此时，第一个指针所指向的节点即为倒数第k个节点。）
- 查找一个字符串中最长的无重复字符子串(查找一个字符串中最长的无重复字符子串，可以使用双指针算法来实现。具体思路是，定义两个指针
left和right，分别表示子串的左右边界，并初始化为字符串的开头。然后移动右指针，直到遇到重复字符为止。此时，我们可以记录下当前子串的长度，并将左指针向右移动，直到遇到重复字符并删除该字符为止。这样，我们就得到了以右指针为结尾的最长无重复字符子串。根据这个方法，我们依次遍历整个字符串，每次更新最长无重复字符子串的长度即可。) public class LongestSubstring {
public static int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int left = 0, right = 0;
int maxLen = 0;
Set<Character> set = new HashSet<>();
while (right < s.length()) {
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
maxLen = Math.max(maxLen, set.size());
} else {
set.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
public static void main(String[] args) {
String s = "abcabcbb";
System.out.println(lengthOfLongestSubstring(s)); // 输出3
}
}
