局部最小值位置、元素最左出现、循环有序数组最小值

た入场券 2022-06-09 05:25 203阅读 0赞

*   *   *  局部最小值位置
         *  元素最左出现
         *  循环有序数组最小值

--------------------

### 局部最小值位置 ###

定义局部最小的概念。arr长度为1时，arr\[0\]是局部最小。arr的长度为N(N>1)时，如果arr\[0\] < arr\[1\]，那么arr\[0\]是局部最小；如果arr\[N-1\]< arr\[N-2\]，那么arr\[N-1\]是局部最小；如果0 < i < N-1，既有arr\[i\]< arr\[i-1\]又有arr\[i\] < arr\[i+1\]，那么arr\[i\]是局部最小。给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。

![这里写图片描述][SouthEast]

**参考答案**

public class Solution { 
        public int getLessIndex(int[] arr) {
            if (arr == null || arr.length == 0) {
                return -1; // no exist
            }
            if (arr.length == 1 || arr[0] < arr[1]) {
                return 0;
            }
            if (arr[arr.length - 1] < arr[arr.length - 2]) {
                return arr.length - 1;
            }
            int left = 1;
            int right = arr.length - 2;
            int mid = 0;
            while (left < right) {
                mid = (left + right) / 2;
                if (arr[mid] > arr[mid - 1]) {
                    right = mid - 1;
                } else if (arr[mid] > arr[mid + 1]) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return left;
        }
    }

--------------------

### 元素最左出现 ###

对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。

给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。

# 测试样例：
    [1,2,3,3,4],5,3
    # 返回：2

**我的提交**

# -*- coding:utf-8 -*-
    
    class LeftMostAppearance:
        def findPos(self, arr, n, num):
            # write code here
            if n <= 0:
                return -1
            if n == 1 and arr[0] == num:
                return 0
            if arr[0] > num:
                return -1
            if arr[n-1] < num:
                return -1
    
            left = 0
            right = n-1
            while left < right:
                print(str(left) + " : " + str(right) + " --> " + str(arr[left:right+ 1]))
                mid = left + (right - left)// 2
                if  num < arr[mid]:
                    right = mid - 1
                elif num > arr[mid]:
                    left = mid + 1
                else:
                    right = mid
            print(str(left) + " : " + str(right) + " --> " + str(arr[left:right+ 1]))
            print()
            if arr[left] == num:
                return left
            return -1
    
    if __name__ == '__main__':
        left = LeftMostAppearance()
        print(left.findPos([1,2,3,3,4],5,3))

**参考答案**

class LeftMostAppearance:
        def findPos(self, arr, n, num):
            res = -1
            lft = 0
            rgt = n - 1
    
            while lft <= rgt:
                mid = lft + (rgt - lft) / 2
                if arr[mid] < num:
                    lft = mid + 1
                elif arr[mid] > num:
                    rgt = mid - 1
                else:
                    res = mid
                    rgt = rgt - 1
            return res

--------------------

### 循环有序数组最小值 ###

对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组\[1,2,3,3,4\]，是有序循环数组，\[4,1,2,3,3\]也是。

给定数组arr及它的大小n，请返回最小值。

#测试样例：
    [4,1,2,3,3],5
    #返回：1

**我的提交**

# -*- coding:utf-8 -*-
    
    class MinValue:
        def getMin(self, arr, n):
            # write code here
            left = 0
            right = n - 1
            if arr[left] < arr[right]:
                return arr[left]
    
            while left < right:
                mid = left + (right - left) // 2
                if arr[left] > arr[mid]:
                    right = mid
                elif arr[mid] < arr[right]:
                    left = mid
                else:
                    mindex = left
                    for i in range(left, right + 1):
                        if arr[i] < arr[mindex]:
                            mindex = i
                    return arr[mindex]

**参考答案**

import java.util.*;
    
    public class MinValue { 
        public int getMin(int[] arr,int n) {
            if (arr == null || arr.length == 0) {
                    return -1;
            }
            int low = 0;
            int high = arr.length - 1;
            int mid = 0;
            while (low < high) {
                if (low == high - 1) {
                    break;
                }
                if (arr[low] < arr[high]) {
                    return arr[low];
                }
                mid = (low + high) / 2;
                if (arr[low] > arr[mid]) {
                    high = mid;
                    continue;
                }
                if (arr[mid] > arr[high]) {
                    low = mid;
                    continue;
                }
                while (low < mid) {
                    if (arr[low] == arr[mid]) {
                        low++;
                    } else if (arr[low] < arr[mid]) {
                        return arr[low];
                    } else {
                        high = mid;
                        break;
                    }
                }
            }
            return Math.min(arr[low], arr[high]);
        }
    }

[SouthEast]: /images/20220609/b4a4f18bf6f44b70a44b5e1e00c1d792.png