java无序数组且相邻不相等中找到局部最小值

本文主要是介绍java无序数组且相邻不相等中找到局部最小值，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

package com.cowain.test;

/**
 * @Author: fxw
 * @Date: 2022/2/26 22:13
 */
public class Code3 {
    //有一个数组无序 并且 相邻不相等 找到局部最小的值
    public static int find(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int N = array.length;
        //当数组长度为1是 直接返回当前元素为最小值
        if (N == 1) {
            return 0;
        }
        //当左边界L<L+1时 直接返回L
        if (array[0] < array[1]) {
            return 0;
        }
        //当右边界R-1<R-2时 直接返回R-1
        if (array[N - 2] > array[N - 1]) {
            return N - 1;
        }
        //以下情况就是长度大于1并且边界条件不满足
        int L = 0;
        int R = N - 1;
        //防止越界处理 L < R-1 即最后只会剩下两个数
        while (L < R - 1) {
            int mid = (L + R) / 2;
            //先是二分法找到中间值 假如 中间值的左边和右边都比他大 那么直接返回中间值
            if (array[mid - 1] > array[mid] && array[mid] < array[mid + 1]) {
                return mid;
            } else {
                //当出现else情况中时 会出现以下三种情况
                // 1  array[mid-1]<array[mid]&&array[mid+1]>array[mid]
                // 1  array[mid-1]>array[mid]&&array[mid]>array[mid+1]
                // 1  array[mid-1]<array[mid]&&array[mid+1]>array[mid]
                if (array[mid] > array[mid - 1]) {//认为0-mid-1中必定有最小值 砍掉mid-R
                    R = mid - 1;
                } else {//认为mid-mid-1中必定有最小值 砍掉L-mid
                    L = mid + 1;
                }
            }
        }
        return array[L] > array[R] ? R : L;
    }

    //生成随机数组 无序 并且 相邻不相等
    public static int[] createRandomArray(int randomIndex, int randomValue) {
        int[] randomArray = new int[(int) (Math.random() * randomIndex)];
        if (randomArray.length > 0) {//判断长度
            randomArray[0] = (int) (Math.random() * randomValue);//给第一个元素复制
            for (int i = 1; i < randomArray.length; i++) {
                do {
                    randomArray[i] = (int) (Math.random() * randomValue);
                } while (randomArray[i] == randomArray[i - 1]);//如果相邻的两个数相等 那么就重新赋值
            }
        }
        return randomArray;
    }

    //编写测试验证方法
    public static boolean check(int[] array, int minIndex) {
        if (array.length == 0 || array == null) {
            return minIndex == -1; //返回false
        }
        int L = minIndex - 1;
        int R = minIndex + 1;
        boolean leftBigger = L > 0 ? array[L] > array[minIndex] : true;
        boolean RightBigger = R < array.length ? array[R] > array[minIndex] : true;
        return leftBigger && RightBigger;
    }

    //打印数组函数
    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + ",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 15;
        int maxValue = 200;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = createRandomArray(maxLen, maxValue);
            int ans = find(arr);
            if (!check(arr, ans)) {
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }
}

这篇关于java无序数组且相邻不相等中找到局部最小值的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！