ae免费模板网站,安徽网站开发项目,建设网站公司哪家技术好,网站未备案wordpress目录
二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)
寻找峰值_牛客题霸_牛客网 (nowcoder.com)
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com) 二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 题意#xff1a…目录
二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)
寻找峰值_牛客题霸_牛客网 (nowcoder.com)
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com) 二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 题意 在一个二维数组array中每个一维数组的长度相同每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。 [ [1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15] ] 给定 target 7返回 true。 给定 target 3返回 false。 数据范围矩阵的长宽满足 0≤n,m≤5000 矩阵中的值满足 0≤val≤10^9 进阶空间复杂度 O(1) 时间复杂度 O(nm) 【输入样例】7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]] 【输出样例】true 解题思路 矩阵的规律是从左到右递增从上到下递增。 选择矩阵的右上角a[row][col]进行对比如果targeta[row][col],证明target在当前列的左边我们可以往左边矩阵寻找 如果targeta[row][col],证明target在当前行的下方我们往下边矩阵寻找 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param target int整型 * param array int整型二维数组 * return bool布尔型*/public boolean Find (int target, int[][] array) {// write code hereint n array.length;int m array[0].length;int row 0;//行int col m-1;//列while(row n col 0){if(target array[row][col]){return true;}else if(target array[row][col]){row;}else{col--;}}return false;}
} 寻找峰值_牛客题霸_牛客网 (nowcoder.com) 题意 给定一个长度为n的数组nums请你找到峰值并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个所在位置即可。 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于 2.假设 nums[-1] nums[n] −∞ 3.对于所有有效的 i 都有 nums[i] ! nums[i 1] 4.你可以使用O(logN)的时间复杂度实现此问题吗 数据范围 1≤nums.length≤2×105 −231nums[i]231−1 输入样例[2,4,1,2,7,8,4] 输出样例1 解题思路 1.暴力枚举只要比上一位大并且比下一位大就是峰值直接返回 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型*/public int findPeakElement (int[] nums) {// write code hereif(nums.length 2 nums[0] nums[1] || nums.length 1){return 0;}if(nums.length 2 nums[nums.length-2] nums[nums.length-1]){return nums.length-1;}for(int i1;inums.length-1;i){if(nums[i] nums[i-1] nums[i] nums[i1]){return i;}}return -1;}
} 解题思路2 二分查找实现时间复杂度为OLogn 跟普通的二分查找一样先计算mid 如果nums[mid] num[mid1]说明mid很可能是峰值我们往左遍历这里与二分查找的区别是往左时候rightmid而不是mid-1因为mid是可能的峰值取值需要在下一轮遍历中进行比较 如果nums[mid] nums[mid1],则说明mid1很可能是一个峰值我们往右边进行遍历left mid1因为mid已经不是可能的峰值取值了所以不包含 通过多轮的遍历最终可以在区间里面找到一个正确的峰值。 如果是单调递增的话每一次都往右走直到leftrightnums.length-1单调递减一直往左走直到leftright0 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型*/public int findPeakElement (int[] nums) {// write code hereif(nums.length 1){return 0;}int left 0;int right nums.length -1;int mid;while(left right){mid (left right) /2;if(nums[mid] nums[mid1]){//mid比下一位大有可能是山峰往左遍历right mid;//注意这里right是赋值mid因为mid可能是山峰所以要包含他去寻找}else{//mid比它下一位小mid1有可能是山峰向右走left mid 1;//从大的数开始往右查找}}return right;}
}
数组中的逆序对_牛客题霸_牛客网 (nowcoder.com) 题目描述 在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007 数据范围 对于 50% 的数据,size≤10^4 对于 100%的数据,size≤10^5 数组中所有数字的值满足 0≤val≤10^9 要求空间复杂度 O(n)时间复杂度 O(nlogn) 【输入样例】[1,2,3,4,5,6,7,0] 【输出样例】7 解题思路1双重循环暴力枚举时间复杂度为O(n^2)运行超时 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型*/public int InversePairs (int[] nums) {// write code hereint ans0;for(int i 0; inums.length-1; i){for(int ji; j nums.length; j){if(nums[i] nums[j]){ans;ans % 1000000007;} }}return ans;}
} 解题思路2 基于归并排序法在合并时候如果右边的数小于左边的数可以直接求出当前产生的逆序对的个数。 import java.util.*;public class Solution {int ans0;public int InversePairs (int[] nums) {// write code hereif(nums.length 2){return 0;}mergeSort(nums,0,nums.length-1);return ans;}public void mergeSort(int[] nums,int left,int right){//分割点int mid (leftright)/2;if(left right){mergeSort(nums,left,mid);mergeSort(nums,mid1,right);//合并merge(nums,left,mid,right);}}public void merge(int[] nums,int left,int mid,int right){//创建临时数组int[] arr new int[right - left 1];//临时数组下标起点int c 0;int s left;int l left;int r mid 1;//左右数组的起始指针while(l mid r right){//当左数组的元素小时跳过if(nums[l] nums[r]){//放入临时数组arr[c] nums[l];c;l;}else{//存在逆序对统计arr[c] nums[r];//逆序对个数ans mid1 - l;ans % 1000000007;c;r;}}//左子数组还有元素放入while(l mid){arr[c] nums[l];}while(r right){arr[c] nums[r];}//临时数组放入数组原位置for(int num: arr){nums[s] num;}}
}
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com) 题目描述 有一个长度为 n 的非降序数组比如[1,2,3,4,5]将它进行旋转即把一个数组最开始的若干个元素搬到数组的末尾变成一个旋转数组比如变成了[3,4,5,1,2]或者[4,5,1,2,3]这样的。请问给定这样一个旋转数组求数组中的最小值。 数据范围1≤n≤10000数组中任意元素的值: 0≤val≤10000 要求空间复杂度O(1) 时间复杂度O(logn) 【输入样例】[3,4,5,1,2] 【输出样例】1 解题思路 将一个非降序的数组进行旋转我们利用二分查找将数组划分为两个子数组时肯定有一个子数组不是有序的 如[left,right] 划分为[left,mid] [mid,right]如果nums[left] nums[mid],证明 [left, mid]区间已经不符合非降序数组的要求了所以这个区间旋转之后变成无序的最小值在这里面寻找 如果是相等则缩小范围继续寻找 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型*/public int minNumberInRotateArray (int[] nums) {// write code hereint left 0;int right nums.length-1;while(left right){int mid (left right) / 2;if(nums[mid] nums[right]){ //右子数组无序left mid 1;}else if(nums[mid] nums[right]){//左子数组无序right mid;}else{//如果是相等的话缩小范围right--;}}return nums[left];}
}
