首页 > 试题广场 >

局部最小值位置

[编程题]局部最小值位置

热度指数：2508 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

定义局部最小的概念。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中任意一个局部最小出现的位置即可。

算法知识视频讲解

小K姐姐

很奇怪，题目不是返回任意局部小位置么，我在二分的时候先转向右半边查找返回后半部分的一个局部小就显示不通过，很奇怪，必须返回第一个局部小的位置？？？

发表于 2017-12-12 14:54:58 回复(3)

还能Free多久

class Solution {
public:
 int getLessIndex(vector<int> arr) {
    if (arr.empty()) return -1;   //一定要有这句，否则出现段错误。。。。。。。
	int len = arr.size();
	if (len == 1 || arr[0]<arr[1]) return 0;
	if (arr[len - 1]<arr[len - 2]) return len - 1;
	int left = 1, right = len - 2;
	while (left <=right) {
		int mid = (left + right) / 2;
		if (arr[mid - 1]<arr[mid]) right = mid - 1;
		else if (arr[mid + 1]<arr[mid]) left = mid + 1;
		else return mid;
	}
	return left;
}
};

发表于 2016-08-19 17:33:58 回复(0)

蓝紫坊

题目关键话：任意两个相邻的数不相等，那么保持条件

	arr[left] < arr[left - 1]



	arr[right] < arr[right + 1]



	则arr[left] 到 arr[right]之间一定有局部最小解

class Solution {
public:
int getLessIndex(vector<int> arr) {
if (arr.empty()){
    return -1;
}
int len = arr.size();
if (len == 1 || arr[0] < arr[1]){    return 0;
}
if (arr[len - 1] < arr[len - 2]){
    return len - 1;
}
int left = 1;
int right = len - 2;
while (left <= right){
    int mid = (left + right) / 2;
    if (arr[mid - 1] < arr[mid]){
        right = mid - 1;
    }
    else if (arr[mid + 1] < arr[mid]){    
        left = mid + 1;
    }
    else{
        return mid;
    }
}
    return 0;//随意返回，程序不会运行到这儿，不加这句，编译不过
}
};

编辑于 2018-10-15 10:29:32 回复(0)

dcjer

根据题目定义：局部最小存在的几种情况，1. 长度为1，arr[0]就是局部最小；2. 数组的开头，如果arr[0] < arr[1] ，arr[0]被定义为局部最小。 3. 数组的结尾，如果arr[N-1] < arr[N-2] ，arr[N-1]被定义为局部最小。所以剩下就是数组下标1~N-2之间的了。再按arr[i-1] < arr[i] <arr[i+1] 找到一个局部最小。题目最后要求返回任意一个。假如你顺序的去搜索，去找一个比左小比右小的数，那么你的时间复杂度为O(N),比如单调递减的数组，搜索到最后一个。使用二分搜索，就能达到O(logN);好像这道题，你如果直接搜索得到的答案是不对的，是不是标准答案的结构就是要你二分搜索，否则任意一个局部最小，答案也不止一个。

发表于 2018-04-12 10:34:19 回复(0)

reyne-d

链接：https://www.nowcoder.com/questionTerminal/322eb1da892448f4b18d9b21a6d48c99
来源：牛客网
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为2.97%
测试用例:
[10,5,10,5,0,1,2,4,7,3,2,9,5,4,6,5,10,6,7,10,9,4,3,7,2,9,5,4,6,10]
对应输出应该为:
4
你的输出为:

？？？这是怎么回事

发表于 2018-02-21 11:02:17 回复(3)

Java

LanternA

public class Solution {

public int getLessIndex(int[] arr) {

if(arr.length == 0) return -1;

if(arr.length == 1) return 0;

return localMinElement(arr, 0, arr.length - 1);

}

private static int localMinElement(int[] a, int start, int end) {

if(a[start] < a[start + 1]) return start;

if(a[end - 1] > a[end]) return end;

int mid = end / 2;

if(a[mid] < a[mid - 1] && a[mid] < a[mid + 1]) return mid;

else {

if(a[mid - 1] < a[mid + 1])

return localMinElement(a, start, mid - 1);

else

return localMinElement(a, mid + 1, end);

}

发表于 2017-06-06 21:30:43 回复(0)

Glenn_Gould


	classSolution {



	public:



	    intgetLessIndex(vector<int> arr)



	    {



	        intsize=arr.size();



	        if(!size)



	            return-1;



	        if(size<2||arr[0]<arr[1])



	            return0;



	        if(arr.back()<arr[size-2])



	            returnsize-1;



	        for(inti=1;i<size-1;i++)



	            if(arr[i]<arr[i-1]&&arr[i]<arr[i+1])



	                returni;



	        return0;



	    }



	};

发表于 2016-09-05 16:20:17 回复(0)

CloudCastle

class Solution {
public:
// 此题的关键在于根据中间元素的大小对数组进行二分
// 解法的时间复杂度为 O(log n)
int getLessIndex(vector<int> arr)
{
    if ( arr.empty() )
        return -1;

    // Size 为 1 直接 return, 不会执行第二个判断
    else if ( arr.size() == 1 || arr[0] < arr[1] )
        return 0;

    if ( arr[arr.size() - 1] < arr[arr.size() - 2] )
        return arr.size() - 1;

    int left = 1;
    int right = arr.size() - 2;
    int mid = 0;

    while ( left < right )
    {
        mid = ( left + right ) >> 1;
        if ( arr[mid] > arr[mid - 1] ) {
            right = mid - 1;
        } else if ( arr[mid] > arr[mid + 1] ) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return left;
}
};

发表于 2015-07-14 21:18:26 回复(0)

wenyanliu

  //这个题并不难，主要是要考虑到所有的临界情况 
  class Solution { 
 public:
     int getLessIndex(vector<int> arr) {
         int n=arr.size();
         if(n==0) return -1;
         if(n==1)return 0;
         if(arr[0]<arr[1])return 0;
         if(arr[n-1]<arr[n-2])return n-1;
         for(int i=1;i<n-1;i++){
             if(arr[i]<arr[i-1]&&arr[i]<arr[i+1])
                 return i;
         }
     }
 };

编辑于 2015-07-01 14:41:43 回复(3)