南京网站专业制作,学习网站建设培训,最新装修风格2023简单大气的,怎样在阿里云做网站题目#xff1a; 给定一个数组arr#xff0c;求出需要排序的最短子数组长度
要求#xff1a; 时间o(n),空间o(1)
思路#xff1a; 有序的数组中#xff0c;任意一个数字#xff0c;一定小于左边的数大于右边的数。 我们找到的需要排序的子数组#xff0c;显然是比右边…题目 给定一个数组arr求出需要排序的最短子数组长度
要求 时间o(n),空间o(1)
思路 有序的数组中任意一个数字一定小于左边的数大于右边的数。 我们找到的需要排序的子数组显然是比右边最小的值大或比左边最大的值小。 我们初始化变量noMinindex-1;从右往左遍历记录经过的最小值为min若当前数大于min说明如果要有序min一定要放 在当前数左边我们更新noMinindex。 也就是说我们的noMinindex是负责记录最左边出现这种情况的位置。我们反方向处理出noMaxindex 他们组成的区间就是最短需要排序的部分了
public class MinLengthForSort {public static int getMinLength(int[] arr) {if (arr null || arr.length 2) {return 0;}int min arr[arr.length - 1];int noMinIndex -1;for (int i arr.length - 2; i ! -1; i--) {if (arr[i] min) {noMinIndex i;} else {min Math.min(min, arr[i]);}}if (noMinIndex -1) {return 0;}int max arr[0];int noMaxIndex -1;for (int i 1; i ! arr.length; i) {if (arr[i] max) {noMaxIndex i;} else {max Math.max(max, arr[i]);}}return noMaxIndex - noMinIndex 1;}public static void main(String[] args) {int[] arr { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };System.out.println(getMinLength(arr));}}题目 给定一个数组找出出现次数超过一半的数字
蠢思路排序找中间
思路 DP扫一遍一个变量count记录解出现的次数是当前解就否则--count为负就换掉当前解。解释想象解全都挨在 一起前面count先达到最大然后减为1或0而其他数字先出现可能会使正确解的count减为负数但都会使正确解 在后面更多从而保证了结束时肯定为正确解
int main()
{int n;//个数scanf(%d,n);int temp,k,count0;while(n--){scanf(%d,temp);if(tempk)count;else{count--;if(count0){count0;ktemp;}}}printf(%d\n,k);
} 题目
给定一个有N×M的整型矩阵matrix和一个整数Kmatrix的每一行和每一列都是排好序的。实现一个函数判断K是否在matrix中。
例如
0 1 2 5
2 3 4 7
4 4 4 8
5 7 7 9
如果K为7返回true如果K为6返回false
要求
时间复杂度为O(NM)额外空间复杂度为O(1)。
思路
1.从矩阵最右上角的数开始寻找row0,colM-1。
2.比较当前数matrix[row][col]与K的关系
如果与K相等说明已找到直接返回true
如果比K大因为矩阵每一列都已排好序所以在当前数所在的列中处于当前数下方的数都会比K大则没有必要继续在第col列上寻找令colcol-1重复步骤2.
如果比K小因为矩阵每一行都已排好序所以在当前数所在的行中处于当前数左方的数都会比K小则没有必要继续在第row行上寻找令rowrow1,重复步骤2.
3.如果找到越界都没有发现与K相等的数则返回false。
或者可以从矩阵的最左下角的数开始寻找rowN-1,col0具体过程类似。
代码
/*** 在行列都排好序的矩阵中找数*/
public class IsContains {public boolean isContains(int[][] matrix, int K) {int row 0;int col matrix[0].length - 1;while (row matrix.length col -1) {if (matrix[row][col] K) {return true;} else if (matrix[row][col] K) {col--;} else {row;}}return false;}
}
