代码随想录算法训练营番外刷题日记0301||29、两数相除，31、下一个排列

29、两数相除

思路：不断相减就是求解的最直接方法，我这样计算时间复杂度有点高

// 时间复杂度O(count*divisor) // 空间复杂度O(1) class Solution { int res = 0; public int divide(int dividend, int divisor) { // dividend 是被除数 if(dividend == 0) return 0; if(divisor == 1) return dividend; if(divisor == -1){ if(dividend == Integer.MAX_VALUE) return -dividend; else if(dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE; // 怕的是特殊情况Integer.MIN_VALUE 除以 -1，那么就超过结果的范围了 } // 不断相减就是求解的最直接方法 int count = 0; long bc = (long)dividend; long c = (long)divisor; if(bc<0 && c<0){ while(bc - c <= 0){ bc -= c; count++; } return count; } else if(bc<0 && c>0){ while(bc + c <= 0){ bc += c; count++; } return -count; } else if(bc>0 && c<0){ while(bc + c >= 0){ bc += c; count++; } return -count; } else{ while(bc - c >= 0){ bc -= c; count++; } return count; } } }  31、下一个排列 // 时间复杂度[ O(nlogn),O(n^2) ) // 空间复杂度O(1) class Solution { public void nextPermutation(int[] nums) { /* 总体思路分成4步 1、从后向前遍历，找到第一次出现递增的两个数，i-1与i是递增的 2、其次找[i,nums.length-1]位置中最接近且比nums[i]大的元素，并与nums[i]交换 3、交换完成后，对于[i,nums.length-1]进行递增的排序 4、输出答案 */ // 分割点就是出现序列变化的地方，因为需要一个更大的序列，所以分割点的位置就是让大的元素向前移动一位的关键位置 int split = -1; int n = nums.length; for(int i=n-1; i>0; i--){ if(nums[i-1] < nums[i]){ // 找到了一次递减的地方 // i-1位置就是分割点 int j = i; int min = i; while(j<n){ // 出现了第一个小于的，说明可以碰到仅次于分割点位置的较大元素了，则交换 if(nums[j] > nums[i-1] && nums[j] < nums[min]){ min = j; } j++; } int temp = nums[min]; nums[min] = nums[i-1]; nums[i-1] = temp; split = i-1; break; } } // 如果整个数组都是递减的，那么整个数组重新排序就可以，split为-1 quickSort(nums, split+1, n-1); } public int[] quickSort(int[] a, int i, int j) { // doQuickSort(a, n, 0, n - 1); doQuickSort(a, j - i + 1, i, j); return a; } // 快速排序 public void doQuickSort(int[] a, int n, int start, int end) { if (n > 1) { int current = a[end]; int minLen = 0;// 小于区间的长度 int i = start; for (; i < end; i++) { if (a[i] < current) {//发现比当前数小的数，扩充小于区间 int temp = a[start + minLen]; a[start + minLen] = a[i]; a[i] = temp; minLen++; } } a[end] = a[start + minLen]; a[start + minLen] = current; //当前位置已经确定，排左右序列 doQuickSort(a, minLen, start, start + minLen - 1); doQuickSort(a, n - minLen - 1, start + minLen + 1, end); } } }