四. 复杂度的oj练习
4.1 轮转数组
解法一：每次旋转一个数字，将最后一个数字放在临时变量中，将数组其他元素向后移动一位，再将临时变量的值放在数组下标为0的位置 ，旋转k次
时间复杂度：O(N*K),K的最坏情况是N-1,所以时间复杂度为O(N^2)
空间复杂度：O(1)
void rotate(int* nums, int numsSize, int k) { k=k%numsSize; for(int i=0;i<k;i++) { int tmp=nums[numsSize-1]; for(int j=numsSize-1;j>0;j--) { nums[j]=nums[j-1]; } nums[0]=tmp; } }
解法二：将前n-k个数字反转，后k个数字反转，在整个反转
时间复杂度：分别一共遍历了俩次数组，O(N)
空间复杂度：O(1)
void reverse(int nums[],int left,int right) { while(left<right) { int tmp=nums[left]; nums[left]=nums[right]; nums[right]=tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { k=k%numsSize; reverse(nums,0,numsSize-k-1); reverse(nums,numsSize-k,numsSize-1); reverse(nums,0,numsSize-1); }
解法三：开辟一个数组，将原数组后k个数据放在新数组的前k个位置，将原数组前n-k个数据放在新数组后n-k个位置，然后将新数组拷贝回去
时间复杂度：O(N)
空间复杂度：O(N)
void rotate(int* nums, int numsSize, int k) { k=k%numsSize; int arr[numsSize]; for(int i=0;i<k;i++) { arr[i]=nums[numsSize-k+i]; } for(int i=0;i<numsSize-k;i++) { arr[k+i]=nums[i]; } for(int i=0;i<numsSize;i++) { nums[i]=arr[i]; } }
4.2 消失的数字
解法一：0^a=a,a^a=0
异或数组所有元素,再与0到n个数字异或，则结果就为缺失的数字
时间复杂度：O(N)
空间复杂度：O(1)
int missingNumber(int* nums, int numsSize){ int tmp=0; for(int i=0;i<numsSize;i++) { tmp=tmp^nums[i]; } for(int i=0;i<=numsSize;i++) { tmp=tmp^i; } return tmp; }
解法二：将0~n个数字累计加起来，然后一一减去数组里面数字，最后的结果就是缺失的数字
时间复杂度：O(N)
空间复杂度：O(1)
int missingNumber(int* nums, int numsSize){ int tmp=numsSize*(numsSize+1)/2; for(int i=0;i<numsSize;i++) { tmp=tmp-nums[i]; } return tmp; }
4.3 移除元素
思路：
因为要求在原地修改数组，所以空间复杂度为O(1)，不能够额外增加空间，那么我们定义俩个下标，dst和scr,将下标scr的值给给下标为dst的值，当nums[scr]！=val，scr++,dst++;scr遇到nums[scr]==val的元素，则scr跳过， dst保持不动,最终dst的值为移除后数组的新长度。
时间复杂度：O(N)
空间复杂度：O(1)
int removeElement(int* nums, int numsSize, int val) { int scr=0; int dst=0; while(scr<numsSize) { if(nums[scr]!=val) { nums[dst]=nums[scr]; scr++; dst++; } else { scr++; } } return dst; }
4.4 删除有序数组的重复项
思路：双指针
要注意题目中已给条件，非严格递增数列，这是解题的关键，遇到重复项，则让重复的后一项的后面的元素向前覆盖掉后重复项
1）当数组长度为1，返回1
2）当数组元素大于2，
如果nums[fast] ≠ nums[slow]，那么nums[slow + 1] = nums[fast]；
如果nums[fast] == nums[slow]，那么指针fast继续向后查找。
时间复杂度：O(N)
空间复杂度：O(1)
int removeDuplicates(int* nums, int numsSize) { if(numsSize==1) { return 1; } int fast=1; int slow=0; while(fast<numsSize) { if(nums[fast]!=nums[slow]) { nums[slow+1]=nums[fast]; slow++; fast++; } else { fast++; } } return slow+1; }
4.5 合并俩个有序数组
思路一：重新创造一个数组，用双指针法，分别指向俩个数组，将小的放入新数组，最后拷贝回nums1数组
时间复杂度：O(n+m)
空间复杂度：O(n+m)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int arr[n+m]; int i=0; int j=0; int k=0; while(i<m&&j<n) { if(nums1[i]>nums2[j]) { arr[k]=nums2[j]; j++; k++; } else { arr[k]=nums1[i]; i++; k++; } } if(i==m) { while(j<n) { arr[k]=nums2[j]; k++; j++; } } if(j==n) { while(i<m) { arr[k]=nums1[i]; k++; i++; } } for(i=0;i<m+n;i++) { nums1[i]=arr[i]; } }
思路二：我们将nums1和nums2和并成一个数组，然后利用快排
int cmp(int* a, int* b) { return *a - *b; } void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { for (int i = 0; i <n; ++i) { nums1[m + i] = nums2[i]; } qsort(nums1, nums1Size, sizeof(int), cmp); }
