算法--数组_牛客博客

1、二维数组中查找目标值

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
暴力解法

public class Solution {
    public boolean Find(int target, int [][] array) {
        
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[i].length;j++){
                if(array[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
}

根据数组规律进行查找
思路：首先该数组的规律是每一行都从左到右递增，每一列都从上到下递增，可以从最左下的元素开始比较，若目标值小于该元素，则搜索范围上移，若目标值大于该元素，则右移

public class Solution {
    public boolean Find(int target, int [][] array) {
        //优先判断特殊
        if(array.length == 0)  
            return false;
        int n = array.length;
        if(array[0].length == 0)  
            return false;
        int m = array[0].length;
        //从最左下角的元素开始往左或往上
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ 
            //元素较大，往上走
            if(array[i][j] > target)   
                i--;
            //元素较小，往右走
            else if(array[i][j] < target) 
                j++;
            else
                return true;
        }
        return false;
    }
}

2、返回峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
思路：直接找到最大值

public class Solution {
    public int findPeakElement(int[] nums) {
            int idx = 0;
            for (int i = 1; i < nums.length; ++i) {
                if (nums[i] > nums[idx]) {
                    idx = i;
                }
            }
            return idx;
        }

}

3、合并区间

链接题目位置
描述：给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。
示例：
思路：先用Collections.sort()将之前的arrayList进行排序，自定义比较大小的方法，然后从最小的一个开始遍历比较
代码：

import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        //创建用于返回的ArrayList
        ArrayList<Interval> res = new ArrayList<>();
        //去除特殊情况,长度为0则返回null
        if(intervals.size() == 0) 
            return res;
        //按照区间首排序,自定义比较方法
        //compare()方法,对象大于目标参数,返回1,对象小于目标参数,返回-1
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2){
                if(o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        }); 
        //放入第一个区间
        res.add(intervals.get(0)); 
        int count = 0;
        //遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++){
            Interval o1 = intervals.get(i);
            Interval origin = res.get(count);
            if(o1.start > origin.end){
                res.add(o1);
                count++;
            //区间有重叠，更新结尾
            }else{ 
                res.remove(count);
                Interval s = new Interval(origin.start, o1.end);
                if(o1.end < origin.end)
                    s.end = origin.end;
                res.add(s);
            }
        }
        return res;
    }
}

4、旋转数组

题目位置
描述：一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
示例：
思路：用该元素现在的位置加上移动的距离，再对数组长度进行取模，即为该元素移动过后的位置
代码：

import java.util.*;

public class Solution {
 
    public int[] solve (int n, int m, int[] a) {
        // write code here
        int[] b=new int[a.length];
        
        for(int i=0;i<a.length;i++){
            b[(i+m)%n]=a[i];
        }
        
        return b;
    }
}