我要招人

去企业版

首页 > 试题广场 >

给定一个整数数组及其长度，存在索引值m与n，使得只需要对m和

[问答题]

给定一个整数数组及其长度，存在索引值m与n，使得只需要对m和n之间的元素进行排序，即可完成整个数组从小到大的排序，试找出m与n之差绝对值最小时的m与n值。

函数原型：int findMinSortRegion（int arr[],int arr_size,int *m,int *n）

示例：数组{1,2,4,7,10,11,7,12,6,7,16,18,19}满足条件的m与n的值为(3,9)

昌西比立斯

#include<iostream>

using namespace std;

int m,n;

void findMinSortRegion(int arr[],int arr_size,int m1,int n1) {

int tag = 0;;

for (int i = 0; i < arr_size-1; i++) {

if (arr[i] < arr[i+1]) {

for (int j = i+1; j < arr_size; j++) {

if (arr[i] == arr[j] || arr[i] > arr[j]) {

m = i;

tag = 1;

break;

}

} else {

m = i;

tag = 1;

break;

}

if (tag == 1) break;

}

tag = 0;

for (int i = arr_size-1; i > 0; i--) {

if (arr[i] > arr[i-1]) {

for (int j = i-1; j >=0; j--) {

if (arr[i] == arr[j] || arr[i] < arr[j]) {

n = i;

tag = 1;

break;

}

} else {

n = i;

}

if (tag == 1) break;

}

int main() {

int length;

int input[100];

cin >> length;

for (int i = 0; i < length;i++) {

cin >> input[i];

}

findMinSortRegion(input,length,m,n);

cout << m << " "<< n;

return 0;

发表于 2017-02-25 22:53:26 回复(0)

cyanlong

此题为寻找最短排序子数组。解题思路是先从左到右遍历数组，用一个变量max记录遍历到当前位置之前的最大值，与当前位置进行比较，如果当前位置大于max，则更新max的值，如果当前位置小于max，说明在排序之后那个max至少要在当前位置或其右侧，我们使用right变量记录最右边的这个位置。

//有数组 A，长度n
int max = A[0], right = 0;
for (int i = 1; i < n; i++){
    if (A[i] > max){
        max = A[i];
    } else {
        right = i;
    }
}

用同样的方式从右往左遍历数组，这时我们记录当排序后最小元素应该到达的位置。

int min = A[n - 1], left = n - 1;
for (int i = n - 2; i >= 0; i--){
    if (A[i] < min){
        min = A[i];
    } else {
        left = i;
    }
}

这样，当right > left 时，它们之间的元素就是待排序的最短子数组。若right < left,说明原数组有序。

编辑于 2017-02-25 16:24:03 回复(0)

hexiaosa

认为这个函数应该返回void，因为m,n已经是指针变量。

void findMinSortRegion(int arr[], int arr_size, int *m, int *n) {
//初始化m和n的值
    m = 0;
    n = arr_size - 1;
    int stop = 0;//用来标识m和n，应该遍历到哪里停止。
    for (; m < n; m++) {
        for (int i = m + 1; i < arr_size; i++) {
            if (arr[i] < arr[m]) {//当第m个后面的数不再都大于第m个时
                stop = 1;
            }
    }
        if (stop == 1) {
            break;
        }
    }//confirm the value of m;
    stop = 0;
    for (; n >= m; n--) {
        for (int i = n - 1; i < arr_size; i--) {
            if (arr[i] > arr[n]) {//当第n个数前面的不再是都小于第n个数时
                stop = 1;
            }
        }
        if (stop == 1) {
            break;
    }//confirm the value of n;
}

编辑于 2017-02-25 10:20:01 回复(0)

提交观点

问题信息

上传者：牛100

难度：

3条回答 38收藏 4392浏览

给定一个整数数组及其长度，存在索引值m与n，使得只需要对m和

问题信息

热门推荐

相关试题