数组基操三连（1）
题目：
给定一个数组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,count=0;
-
while(n--)
-
{
-
scanf("%d",&temp);
-
if(temp==k)count++;
-
else
-
{
-
count--;
-
if(count<0){count=0;k=temp;}
-
}
-
}
-
printf("%d\n",k);
-
}
题目：
给定一个有N×M的整型矩阵matrix和一个整数K，matrix的每一行和每一列都是排好序的。实现一个函数，判断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(N+M)，额外空间复杂度为O(1)。
思路：
1.从矩阵最右上角的数开始寻找（row=0,col=M-1）。
2.比较当前数matrix[row][col]与K的关系：
如果与K相等，说明已找到，直接返回true
如果比K大，因为矩阵每一列都已排好序，所以在当前数所在的列中，处于当前数下方的数都会比K大，则没有必要继续在第col列上寻找，令col=col-1，重复步骤2.
如果比K小，因为矩阵每一行都已排好序，所以在当前数所在的行中，处于当前数左方的数都会比K小，则没有必要继续在第row行上寻找，令row=row+1,重复步骤2.
3.如果找到越界都没有发现与K相等的数，则返回false。
或者可以从矩阵的最左下角的数开始寻找（row=N-1,col=0），具体过程类似。
代码：
-
/**
-
* 在行列都排好序的矩阵中找数
-
*/
-
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;
-
}
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/90270402
- 点赞
- 收藏
- 关注作者
评论（0）