/**
* 力扣第283题：
* https://leetcode-cn.com/problems/move-zeroes/
*
* 将所有的0移动到数组的末尾
*/
public class LeetCodeTest01 {
public static void main(String[] args) {
//准备数据
int[] arr = {4,2,4,0,0,3,0,5,1,0};//预期结果：4,2,4,3,5,1,0,0,0,0
// int[] arr = {0,1,0,3,12};
// int[] arr = {0,0,1};
System.out.println("移动零前的数组："+Arrays.toString(arr));
//方法1：写两层循环
// moveZero1(arr);
//方法2：新开一个数组将所有的0依次放到新数组的末尾
// moveZero2(arr);
//方法3：一层循环，做下标移动
moveZero3(arr);
System.out.println("移动零后的数组："+Arrays.toString(arr));
}
/**
* 仅仅是使用一个变量去记录非0元素
* 最后需要存放的位置，然后遍历过程中
* 交换即可。
* 时间复杂度：O(n)
* 空间复杂度：O(1)
* @param arr 需要处理的数组
*/
private static void moveZero3(int[] arr) {
//用于记录非0元素的下标
int j = 0;
for (int i = 0; i < arr.length; i++) {
//如果为0就跳过，我们只处理非0元素
if(arr[i] == 0){
continue;
}
//将非0元素和0的下标位置进行交换
int tmp = arr[i] ^arr[j];
arr[i] ^= tmp;
arr[j] ^= tmp;
j++;
}
}
/**
* 使用新开一个数组的方法实现
* 与题目要求不相符，题目要求不能新开辟一个其它数组，
* 只能在原有数组上进行操作。
* 时间复杂度：O(n)
* 空间复杂度：O(n)
* @param arr 需要处理的数组
*/
private static void moveZero2(int[] arr) {
int[] result = new int[arr.length];
for (int i = 0,j=0; i < arr.length; i++) {
//如果为0就跳过
if(arr[i] == 0){
continue;
}
//将非0数放到新数组的前面
result[j] = arr[i];
j++;
}
//将结果数组复制到入参中
System.arraycopy(result, 0, arr, 0, result.length);
}
/**
* 使用嵌套for循环方式实现
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
* @param arr 需要处理的数组
*/
private static void moveZero1(int[] arr) {
int zeroCount = 0;
for (int i = 0; i < arr.length; i++) {
//如果不为0就跳过本次循环
if(arr[i] != 0){
continue;
}
zeroCount++;
if(i+1 < arr.length && arr[i+1] == 0){
continue;
}
/*
* 如果为0就将其删除：将后面的元素往前挪
* 有多少个0就挪多少位
*/
for (int j = i+1; j < arr.length; j++) {
//将后面的元素往前挪的操作
arr[j-zeroCount] = arr[j];
}
for (int j = 1; j <= zeroCount; j++) {
arr[arr.length-j] = 0;
}
/*
* 移位之后需要将外层的循环变量重置到
* 移动0后的起始位的下一位开始，
* 否则会导致移位后的0没有被处理，
* 如果不加1就会导致死循环
*/
i = i - zeroCount + 1;
zeroCount = 0;
}
}
}
/**
* 力扣第26题：
* https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
*
* 删除排序数组中的重复项
*/
public class LeetCodeTest02 {
public static void main(String[] args) {
//准备数据
// int[] arr = {1,1,2};
int[] arr = {0,0,1,1,1,2,2,3,3,4};
System.out.println("处理前的数组："+Arrays.toString(arr));
//方法1：穷举
// int length = removeDuplicates1(arr);
//方法2：另外开辟一个空间去判断
// int length = removeDuplicates2(arr);
//方法3：双指针
int length = removeDuplicates3(arr);
System.out.println("处理后的数组："+Arrays.toString(arr) +"长度为："+ length);
System.out.println("处理后的数组："+ArrayUtils.toString(arr, 0, length));
}
/**
* 双指针法：
* 注意：这个前提是这个数组是已经排好序了
* 时间复杂度为：O(n)
* 空间复杂度为：O(1)
* @param arr 需要处理的数组
* @return 处理后的数组的长度
*/
private static int removeDuplicates3(int[] arr) {
//定义一个变量用于记录最后一个不重复元素的下标
int i = 0;
//从第二个元素开始遍历数组
for (int j = 1; j < arr.length; j++) {
//当i下标的值和j下标的值相同时就跳过本次循环
if(arr[i] == arr[j]){
continue;
}
/*
* 当i下标的值和j下标的值不同时
* 就让i往后移1位后交换下标i和j的值
*/
i++;
arr[i] = arr[j];
}
//最后返回最后一个不重复元素的下标+1就是数组的长度
return i + 1;
}
/**
* 另外开辟一个数组空间进行处理方式
* 虽然使用了两个for循环，但是两个for循环是并列关系
* 所以时间复杂度：O(n)
* 但是不符合题意的要求不能另外开辟数组空间
* 由于另外开辟了一个数组空间，所以空间复杂度为：O(n)
* @param arr 需要处理的数组
* @return 处理后的数组的长度
*/
private static int removeDuplicates2(int[] arr) {
//由于需要保证有序所以使用LinkedHashSet
Set<Integer> arrSet = new LinkedHashSet<>();
//遍历数组将其每一个元素装进Set中
for (int i = 0; i < arr.length; i++) {
arrSet.add(arr[i]);
}
//再将Set中的元素装回数组中
Object[] array = arrSet.toArray();
for (int i = 0; i < array.length; i++) {
arr[i] = (int)array[i];
}
return array.length;
}
/**
* 暴力方式：穷举
* 由于使用了3层循环，所以
* 时间复杂度：O(n^3)
* 空间复杂度：O(1)
* @param arr 需要处理的数组
* @return 处理后的数组的长度
*/
private static int removeDuplicates1(int[] arr) {
//新数组的长度：假设所有元素都不重复则为原数组长度
int length = arr.length;
/*
* 遍历数组
* 注意：如果已经到了最后一个元素，那么肯定没有重复的了
* 所以不用遍历最后一个元素，因此是arr.length - 1
*/
for (int i = 0; i < length - 1; i++) {
//从下一个元素开始查找是否有相等的
for (int j = i+1; j < length; j++) {
//如果不相等说明不是重复的元素，跳过本次循环
if(arr[i] != arr[j]){
continue;
}
//然后将之后的元素都往前挪一位
for (int k = j; k < length - 1; k++) {
arr[k] = arr[k+1];
}
//如果相等说明有重复的元素，就让length自减1
length--;
/*
* 由于进行了往前挪一位，所以需要重置j的位置到j-1
* 从j-1位置继续往后比较
*/
j--;
}
// System.out.println("第"+(i+1)+"次循环的数组："+Arrays.toString(arr));
}
return length;
}
}
/**
* 力扣第189题：
* https://leetcode-cn.com/problems/rotate-array/
* 旋转数组
* @author Peter
*/
public class LeetCodeTest03 {
public static void main(String[] args) {
//准备数据
int[] arr = {1,2,3,4,5,6,7};
int k = 3;
System.out.println("处理前的数组："+Arrays.toString(arr));
// rotate1(arr,k);
// rotate2(arr,k);
// rotate3(arr,k);
rotate4(arr,k);
System.out.println("处理后的数组："+Arrays.toString(arr));
}
/**
* 暴力方式：嵌套循环将每个元素依次往后挪
* 总共挪k次，就是往后挪了k位
* 由于使用了嵌套循环所以
* 时间复杂度为：O(k*n)
* 空间复杂度为：O(1)
* @param arr 需要处理的数组
* @param k 需要往后移动的位数
*/
private static void rotate1(int[] arr, int k) {
//排除特殊情况
if(arr == null || arr.length <=1){
return;
}
//由于需要往后挪k位，所以需要循环k次
for (int i = 0; i < k; i++) {
//声明一个临时变量用于记录被覆盖的数
int tmp = 0;
//用于保存上一个数的变量
int previous = arr[0];
//往后挪1位
for (int j = 0; j < arr.length ; j++) {
//如果是最后一个元素就直接放到第一个下标上去
if(j == arr.length-1){
arr[0] = tmp;
continue;
}
tmp = arr[j+1];
arr[j+1] =previous;
previous = tmp;
}
}
}
/**
* 另外开辟一个数组空间进行处理方式
*
* 时间复杂度为：O(n)
* 由于使用了额外的数组空间所以
* 空间复杂度为：O(n)
* @param arr 需要处理的数组
* @param k 需要往后移动的位数
*/
private static void rotate2(int[] arr, int k) {
//用一个数组去存放旋转后的结果
int[] resultArr = new int[arr.length];
//首先将数组中的元素放到其旋转后正确的位置
for (int i = 0; i < arr.length; i++) {
//使用取模的方式去处理下标越界的问题
resultArr[(i+k) % resultArr.length] = arr[i];
}
//不能这样，因为Java是值传递的
// arr = resultArr;
//然后将处理好的数组复制到原数组中
System.arraycopy(resultArr, 0, arr, 0, arr.length);
}
/**
* 环状替换方式，易于理解参考：
* https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-yuan-di-huan-wei-xiang-xi-tu-jie/
* 时间复杂度为：O(n)
* 空间复杂度为：O(1)
* @param arr 需要处理的数组
* @param k 需要往后移动的位数
*/
private static void rotate3(int[] arr, int k) {
//如果k > arr.length 那么其移动的步数就为其取余arr.length后的步数
k %= arr.length;
// 记录交换位置的次数，n个同学一共需要换n次
int count = 0;
//对每一个元素将其放到最后的位置
for(int i = 0; count < arr.length; i++) {
int cur = i; // 从0位置开始换位子
do{
//得到其应该存放的下标
int next = (cur + k) % arr.length;
//先保存一下要被替换的下标的值
int temp = arr[next]; // 来到角落...
//开始交换
arr[next] = arr[i];
arr[i] = temp;
//下一次循环从被挤走的数的下标开始
cur = next;
count++;
}while(i != cur) ; // 循环暂停，回到起始位置，角落无人
}
}
/**
* 反转方法实现
*
* 时间复杂度为：O(n)
* 空间复杂度为：O(1)
* @param arr 需要处理的数组
* @param k 需要往后移动的位数
*/
private static void rotate4(int[] arr, int k) {
//首先反转整个数组
reverse(arr, 0, arr.length-1);
//然后反转前(k取余arr.length)个数
k %= arr.length;
reverse(arr, 0, k-1);
//再反转后面n-k个数即可得到最终结果
reverse(arr, k, arr.length-1);
}
/**
* 反转数组的方法
* @param arr 需要被反转的数组
* @param start 需要被反转的起始下标
* @param end 需要被反转的结束下标
*/
private static void reverse(int[] arr, int start, int end) {
/*
* 当左下标小于右下标时不断交换两个数
* 当交换完毕之后整个数组就达到了反转的效果
*/
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
//两边指针不断往中间靠
start++;
end--;
}
}
}