做网站一般需要哪些文件夹?,江苏省住房和城乡建设厅 官方网站,做网站软件有哪些,网站建设方案目录文章目录 二分查找顺序查找二分查找迭代写法二分查找递归写法元素中有重复元素的二分查找在排序数组中查找元素的第一个和最后一个位置山脉数组的峰顶索引旋转数字的最小数字找缺失数字优化求平方根二叉搜索树中搜索指定值验证二叉搜索树有序数组转化为二叉搜索树 快速排序以第… 文章目录 二分查找顺序查找二分查找迭代写法二分查找递归写法元素中有重复元素的二分查找在排序数组中查找元素的第一个和最后一个位置山脉数组的峰顶索引旋转数字的最小数字找缺失数字优化求平方根二叉搜索树中搜索指定值验证二叉搜索树有序数组转化为二叉搜索树 快速排序以第一个元素为基准实现快速排序以最后一个元素为基准实现快速排序以中间元素为基准实现快速排序 归并排序归并排序 二分查找
顺序查找
逐个遍历判断是否是待查找的元素
public int search(int[] array,int key){for(int i0;iarray.length;i){if(array[i]key){return i;}}return -1;
}二分查找迭代写法
有序数组可用可作为模板记忆注意边界
public int binarySearch(int[] array,int key,int low,int high){while (low high){int mid low((high-low)1);if(array[mid]key){return mid;}else if(array[mid]key){high mid - 1;}else if(array[mid]key){low mid 1;}}return -1;
}二分查找递归写法
有序数组可用可作为模板记忆注意边界
public int binarySearch(int[] array,int key,int low,int high){if(lowhigh){int mid low((high-low)1);if(array[mid]key){return mid;}else if(array[mid]key){return binarySearch(array,key,low,mid-1);}else if(array[mid]key){return binarySearch(array,key,mid1,high);}}return -1;
}元素中有重复元素的二分查找
基于模板找到元素后继续向前遍历找到等于待查找元素在数组中首次出现的位置如果元素过多也可使用二分查找方式继续查找
public int binarySearchRe(int[] array, int key, int low, int high) {while (low high) {int mid low ((high - low) 1);if (array[mid] key) {while (mid 0 array[mid] key) {mid--;}return mid 1;} else if (array[mid] key) {high mid - 1;} else if (array[mid] key) {low mid 1;}}return -1;
}在排序数组中查找元素的第一个和最后一个位置
基于模板找到元素后继续向前、后遍历找到等于待查找元素在数组中首次出现的位置和最后出现的位置如果元素过多也可使用二分查找方式继续查找
public int[] searchRange(int[] nums, int target) {return binarySearch(nums,target,0,nums.length-1);
}public int[] binarySearch(int[] nums,int target,int low,int high){int[] res new int[]{-1,-1};while(lowhigh){int mid low ((high-low)1);if(nums[mid]target){int left mid;while(left0nums[left]target){left--;}int right mid;while(rightnums.lengthnums[right]target){right;}res[0] left1;res[1] right-1;return res;}else if(nums[mid]target){high mid-1;}else if(nums[mid]target){low mid1;}}return res;
}山脉数组的峰顶索引
注意山脉的判断条件高于两侧数据递增顺序在左侧递减顺序在右侧
public int peakIndexInMountainArray(int[] arr) {int high arr.length-2;int low 1;while(low high){int mid low((high-low)1);if(arr[mid]arr[mid-1] arr[mid]arr[mid1]){return mid;}else if(arr[mid]arr[mid-1] arr[mid]arr[mid1]){low mid1;}else if(arr[mid]arr[mid-1] arr[mid]arr[mid1]){high mid - 1;}}return -1;
}旋转数字的最小数字
使用二分查找模板边界值通过测试样例确定
public int findMin(int[] nums) {int low 0;int high nums.length - 1;while(lowhigh){int mid low((high-low)1);if(nums[mid]nums[high]){low mid1;}else if(nums[mid]nums[high]){high mid;}}return nums[low];
}找缺失数字
使用二分查找模板边界值通过测试样例确定
public int missingNumber(int[] array){int high array.length;int low 0;while (lowhigh){int mid low ((high - low)1);if(array[mid] mid){low mid1;}else{high mid - 1;}}return low;
}优化求平方根
使用二分查找模板边界值通过测试样例确定
public int mySqrt(int x) {int low 1;int high x;while(low high){int num low ((high-low)1);if(x/num num){return num;}else if(x/numnum){low num 1;}else{high num - 1;}}return high;
}二叉搜索树中搜索指定值
二分查找与二叉树的结合先判断根节点根据根节点与待查找值的情况判断在左子树或者右子树查找
public TreeNode searchBST(TreeNode root, int val) {if(rootnull){return null;}else if(root.val val){return root;}else if(root.valval){return searchBST(root.right,val);}else if(root.valval){return searchBST(root.left,val);}return null;
}验证二叉搜索树
限定low和high两个范围进行验证验证左右子树时根据根节点的值更新low和high
public boolean isValidBST(TreeNode root) {long low Long.MIN_VALUE;long high Long.MAX_VALUE;return isValidBST(root,low,high);
}public boolean isValidBST(TreeNode root,long low,long high){if(rootnull){return true;}if(root.vallow || root.val high){return false;}return isValidBST(root.left,low,root.val)isValidBST(root.right,root.val,high);
}有序数组转化为二叉搜索树
每次选择中间值作为根节点再通过左右两个序列创建左右子树
public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums,0,nums.length-1);
}public TreeNode sortedArrayToBST(int[] nums,int left,int right){if(leftright){return null;}int mid left((right-left)1);TreeNode root new TreeNode(nums[mid]);root.left sortedArrayToBST(nums,left,mid-1);root.right sortedArrayToBST(nums,mid1,right);return root;
}快速排序
以第一个元素为基准实现快速排序
快速排序模板1
public void quickSort(int[] array, int left, int right) {if(leftright){int pivot array[left];int i right 1;for (int j right; j left; j) {if (array[j] pivot) {i--;int temp array[j];array[j] array[i];array[i] temp;}}int pivotIndex i - 1;int temp array[left];array[left] array[pivotIndex];array[pivotIndex] temp;quickSort(array,left,pivotIndex-1);quickSort(array,pivotIndex1,right);}
}以最后一个元素为基准实现快速排序
快速排序模板2
public void quickSort(int[] array, int left, int right) {if (left right) {int pivot array[right];int i left - 1;for (int j left; j right; j) {if (array[j] pivot) {i;int temp array[i];array[i] array[j];array[j] temp;}}int pivotIndex i 1;int temp array[pivotIndex];array[pivotIndex] array[right];array[right] temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex 1, right);}
}以中间元素为基准实现快速排序
快速排序模板3
public static void quickSort(int[] array, int start, int end) {if (start end) {return;}int left start;int right end;int mid (left right) / 2;int pivot array[mid];while (left right) {while (left right array[left] pivot) {left;}while (left right array[right] pivot) {right--;}if (left right) {int temp array[left];array[left] array[right];array[right] temp;left;right--;}}quickSort(array, start, right);quickSort(array, left, end);
}归并排序
归并排序
归并排序模板
public void mergeSort(int[] array, int start, int end, int[] temp) {//2.直至每个序列只包含一个元素停止划分if (start end) {return;}//1.从中间开始每次划分为两个序列mergeSort(array, start, (start end) / 2, temp);mergeSort(array, (start end) / 2 1, end, temp);//3。进行有序数组的合并merge(array, start, end, temp);
}public void merge(int[] array, int start, int end, int[] temp) {//找到序列中点int mid (start end) / 2;//left遍历左边的序列int left start;//right遍历右边的序列int right mid 1;//index遍历临时数组存储合并结果int index 0;//两个序列均从起点到终点进行遍历while (left mid right end) {//将两个序列中较小的元素放入临时数组中if (array[left] array[right]) {temp[index] array[left];}else {temp[index] array[right];}}//此时仅剩一个序列未遍历结束直接赋值while (left mid){temp[index] array[left];}while (rightend){temp[index] array[right];}//将归并的结果拷贝到原数组for (int istart;iend;i){array[i] temp[i];}
}数组中第K大的数的问题可以通过数组排序解决根据题目中给定的时间、空间复杂福选择合适的排序算法
