小Q在学习许多排序算法之后灵机一动决定自己发明一种排序算法，小Q希望能将n个不同的数排序为升序。小Q发明的排序算法在每轮允许两种操作：
1、 将当前序列中前n-1个数排为升序
2、 将当前序列中后n-1个数排为升序
小Q可以任意次使用上述两种操作，小Q现在想考考你最少需要几次上述操作可以让序列变为升序。
[编程题]小Q的排序
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* aMin: 序列中的最小值
* aMax: 序列中的最大值
*
* 分三种情况：
* (1)aMin和aMax都在正确位置，即 aMin==a[0] && aMax==a[n-1]
* (2)aMin和aMax都不在正确位置，即 aMin!=a[0] && aMax!=a[n-1]
* (3)aMin和aMax只有一个在正确位置，即 aMin==a[0] || aMax==a[n-1]
*
* res: 使整个序列变为升序所需要的最少操作次数
* 对于第一种情况：如果原序列已是升序，则res=0，否则res=1
* 对于第二种情况：如果aMax==a[0] && aMin==a[n-1]，则res=3，否则res=2
* 对于第三种情况：res=1
*
* @author wylu
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = br.readLine()) != null) {
int n = Integer.parseInt(line);
int[] a = new int[n];
String[] strs = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(strs[i]);
}
int aMin = a[0], aMax = a[0], res;
boolean isSorted = true;
for (int i = 1; i < n; i++) {
aMin = Math.min(aMin, a[i]);
aMax = Math.max(aMax, a[i]);
if (a[i - 1] > a[i]) isSorted = false;
}
if (aMin != a[0] && aMax != a[n - 1]) res = (aMax == a[0] && aMin == a[n-1]) ? 3 : 2;
else res = isSorted ? 0 : 1;
System.out.println(res);
}
}
}
编辑于 2019-04-26 10:33:04
回复(2)
1.先判断是否需要排序，不需要输出0
2.统计数组的最大值maxx和最小值minn，看原数组最后一个数与maxx和minn之间的关系：
- 如果nums[n-1]==maxx，输出1（只需要排一次前n-1个数）
- 如果minn<nums[n-1]<maxx，输出2（先排好前n-1个，然后把最后一个数放在非第一个的合适的位置）
- 如果nums[n-1]==minn，输出3（最后一个数要三次才能放在第一位）
#include<iostream>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
int solve(vector<int>& nums, int n){
vector<int> nums_bak = nums;
sort(nums_bak.begin(),nums_bak.end());
bool needSort = false;
for (int i=0;i<n;i++){
if (nums_bak[i]!=nums[i]) needSort = true;
}
if (!needSort) return 0;
int maxx = INT_MIN, minn = INT_MAX;
for (auto d:nums){
if (d>maxx) maxx = d;
if (d<minn) minn = d;
}
if (nums[n-1]==maxx) return 1;
if (nums[n-1]==minn) return 3;
else return 2;
}
int main(){
int n;
cin>>n;
vector<int> nums(n,0);
for (int i=0;i<n;i++) cin>>nums[i];
cout<<solve(nums,n)<<endl;
}
发表于 2019-03-10 16:59:40
回复(5)
在输入数据的过程中求取最大和最小值，并判断数组的有序性。分为以下三种情况：
1.最大和最小值都在正确的位置上：如果数组有序，则无需操作，否则只需要一次操作。
2.最大和最小值都不在正确的位置上：如果最大值在排头，最小值在排尾，需要三次操作（因为无论考虑前n-1个数还是后n-1个数，一次操作都不能使得两个最值归位），否则需要两次。
3.最大和最小值只有一个不在正确的位置上：此时仅需要一次操作。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] strArr = br.readLine().trim().split(" ");
int[] arr = new int[n];
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
boolean isSorted = true;
// 从数组中找到最大值和最小值，并判断有序性
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(strArr[i]);
if(min > arr[i]) min = arr[i];
if(max < arr[i]) max = arr[i];
if(i == 0)
continue;
else
if(arr[i - 1] > arr[i]) isSorted = false;
}
if(arr[0] == min && arr[n - 1] == max){
// 如果最大值和最小值都在正确的位置
if(isSorted) // 如果已经有序就无需操作
System.out.println(0);
else
System.out.println(1);
}else if(arr[0] != min && arr[n - 1] != max){
// 如果最大值和最小值都不在正确的位置
if(arr[0] == max && arr[n - 1] != min) // 最大最小值完全相反需要3次排序
System.out.println(3);
else
System.out.println(2);
}else if(arr[0] != min || arr[n - 1] != max){
// 如果最大值和最小值有一个不在正确的位置
System.out.println(1);
}
}
}
编辑于 2021-02-06 16:39:34
回复(0)
虽然问题不难，但是逻辑还是要一步一步屡清楚。
1.当初始输入已经是升序时，如1 2 3 4 5 6，此时不需要进行排序，输出为0；
2.当初始输入不是升序时：以4 3 6 2 1 5为例
1>首先前N-1个数进行升序排序，执行完这次动作之后，得到的是一个已经按升序排列并且长度为N-1的数组加上原数组的最后一个数，即1 2 3 4 6 5
然后需要判断是否有必要进行后N-1个数的排序动作。
a.假如最后一个数大于前N-1个数中的任意一个（或者说前N-1个数排序后的最后一个数），那么就无须再进行后N-1个数进行排序，输出1
b.假如最后一个数比较小，那么就有必要进行后N-1个数排序动作，这个动作执行完之后会有两种情况：
一、当最后一个数大于前N-1个数中的最小的数时，那么经过b的排序之后，升序完成，输出2
二、当最后一个数比前N-1个数中的最小的数还小时，那么经过b之后，它就变成一个数（第二小）加上一个已经是升序的数组，很明显，还需要对前N-1个数执行一次排序动作，即输出3
代码比较水，就不列了。
换成数学的逻辑语言描述如下(表述能力有限，谅解)：
输入长度为i的数列
发表于 2020-06-13 21:39:40
回复(0)
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
while(scan.hasNext()){
int n=scan.nextInt();
int d0=0;
int dl=0;
int pre=0;
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
int ans=0;
for(int i=0;i<n;i++){
int tem=scan.nextInt();
if(pre>tem)
ans=1;
pre=tem;
if(i==0)
d0=tem;
if(i==n-1)
dl=tem;
max=Integer.max(max,tem);
min=Integer.min(min,tem);
}
if(ans==0){
System.out.println(0);
}else{
if (min == d0) {
System.out.println(1);
}else if (max == dl) {
System.out.println(1);
}else if((d0==max&&dl!=min)||(d0!=max&&dl==min)){
System.out.println(2);
}else if(d0==max&&dl==min){
System.out.println(3);
}else{
System.out.println(2);
}
}
}
}
}
发表于 2019-04-24 22:39:54
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
int[] brr = new int[n];
for(int i=0;i<n;i++){
brr[i] = arr[i];
}
Arrays.sort(brr);
if(brr[0] == arr[0]||brr[n-1] == arr[n-1]){
System.out.println(1);
}else if(brr[0] == arr[n-1]&&brr[n-1] == arr[0]){
System.out.println(3);
}else{
System.out.println(2);
}
}
}
发表于 2019-01-15 18:50:22
回复(1)
#include <bits/stdc++.h>
using namespace std;
int main()
{ int n; while(cin>>n) { int a[n],Min=0X7f7f7f7f,Max=-1,p1=0,p2=0; for(int i=0;i<n;i++) { cin>>a[i]; if(a[i]<Min) { Min = a[i]; p1 = i; } if(a[i]>Max) { Max = a[i]; p2 = i; } } bool isSorted = true; int res = 0; if(p1==0 && p2==n-1) { for(int i=1;i<n;i++) { if(a[i]<a[i-1]){ isSorted = false; break; } } if(isSorted) res = 0; else res = 1; }else if(p1!=0 && p2!=n-1){ res = 2; }else if(p1==0 || p2==n-1){ res = 1; } cout<<res<<endl; } return 0;
}
发表于 2019-01-10 22:36:20
回复(0)
import java.util.*;
public class Main {
private static final int INT_MAX = 0X3F3F3F3F;
private static final int INT_MIN = -0X3F3F3F3F;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int min = INT_MAX, minIndex = -1, max = INT_MIN, maxIndex = -1;
int ans = 2; int last = INT_MAX; boolean lastFlag = true;
for (int i=1; i<=n; i++) {
int now = sc.nextInt();
if (last != INT_MAX && last > now) {
lastFlag = false;
}
last = now;
if (now 1) { break; } }
if (now > max) { max = now; maxIndex = i; }
}
if (lastFlag) { ans = 0; }
else if (maxIndex == n || minIndex == 1 ) { ans = 1; }
System.out.println(ans);
return;
}
}
编辑于 2019-02-12 16:39:00
回复(3)
# 看起来是个排序，其实是分情况讨论，排序的内容对外是黑盒
# 原来就是有序的，不用排序0
# 最小值在第一个或者最大值在最后一位，排序一次1
# 最大值在第一位且最小值在最后一位，排序3次
# 其他情况排序2次
n = int(input())
num = list(map(int, input().split()))
if num[:] == sorted(num):
print(0)
elif num[0] == min(num) or num[-1] == max(num):
print(1)
elif num[0] == max(num) and num[-1] == min(num):
print(3)
else:
print(2)
# 原来就是有序的，不用排序0
# 最小值在第一个或者最大值在最后一位，排序一次1
# 最大值在第一位且最小值在最后一位，排序3次
# 其他情况排序2次
n = int(input())
num = list(map(int, input().split()))
if num[:] == sorted(num):
print(0)
elif num[0] == min(num) or num[-1] == max(num):
print(1)
elif num[0] == max(num) and num[-1] == min(num):
print(3)
else:
print(2)
发表于 2020-07-20 15:44:46
回复(0)
package main
import (
"fmt"
)
func main() {
var n int
fmt.Scan(&n)
max,min:=0,1000000001
arr:=make([]int,n)
for i:=0;i<n;i++{
fmt.Scan(&arr[i])
if arr[i]>max{
max=arr[i]
}
if arr[i]<min{
min=arr[i]
}
}
if arr[n-1]==max||arr[0]==min{
fmt.Print(1)
return
}
fmt.Print(2)
}
发表于 2023-06-04 14:40:35
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, res = 0;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++){
cin >> v[i];
}
while(!is_sorted(v.begin(), v.end())){
sort(v.begin(), v.end() - 1);
sort(v.begin() + 1, v.end());
res += 2;
}
cout << res;
return 0;
}
发表于 2023-01-11 16:50:15
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int[] a = new int[n];
for(int i =0;i<n;i++){
arr[i] = sc.nextInt();
a[i] = arr[i];
}
Arrays.sort(a);
boolean b = true;
for(int i =0;i<n;i++){
if(a[i]!=arr[i]){
b = false;
break;
}
}
if(b)
System.out.println(0);
else if(a[0]==arr[0]||a[n-1]==arr[n-1]){
System.out.println(1);
}else if(a[0] == arr[n-1]&&a[n-1] == arr[0]){
System.out.println(3);
}else{
System.out.println(2);
}
}
}
发表于 2021-08-25 16:08:13
回复(0)
分四种情况
#include <iostream>
#include <climits>
using namespace std;
// 判断最大值最小值位置？
int main() {
int n, min = INT_MAX, max = INT_MIN, min_index, max_index;
int val, last_val = INT_MIN, flag = 2;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> val;
if (val < last_val) flag = 0; // 输入序列不是升序
last_val = val;
// max尽可能靠右：>=
if (val >= max) {
max = val;
max_index = i;
}
// min尽可能靠左：<
if (val < min) {
min = val;
min_index = i;
}
}
if (flag) cout << 0 << endl;
else if (min_index == 1 || max_index == n) cout << 1 << endl;
else if (min_index == n && max_index == 1) cout << 3 << endl;
else cout << 2 << endl;
return 0;
}
发表于 2021-03-26 14:41:49
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
int n;
long long a;
while(std::cin>>n)
{
std::vector<long long>s;
for(int i=0;i<n;i++)
{
std::cin>>a;
s.push_back(a);
}
int max_index=std::max_element(s.begin(),s.end())-s.begin();
int min_index=std::min_element(s.begin(),s.end())-s.begin();
if(max_index==n-1||min_index==0)std::cout<<1<<std::endl;
if(min_index>0&&min_index<=n-2&&min_index>0&&min_index<=n-2)std::cout<<2<<std::endl;
if(max_index==0&&min_index>0&&min_index<=n-2)std::cout<<2<<std::endl;
if(max_index==0&&min_index==n-1)std::cout<<3<<std::endl;
if(min_index==n-1&&max_index>0&&max_index<=n-2)std::cout<<2<<std::endl;
}
return 0;
}
#include<vector>
#include<algorithm>
int main()
{
int n;
long long a;
while(std::cin>>n)
{
std::vector<long long>s;
for(int i=0;i<n;i++)
{
std::cin>>a;
s.push_back(a);
}
int max_index=std::max_element(s.begin(),s.end())-s.begin();
int min_index=std::min_element(s.begin(),s.end())-s.begin();
if(max_index==n-1||min_index==0)std::cout<<1<<std::endl;
if(min_index>0&&min_index<=n-2&&min_index>0&&min_index<=n-2)std::cout<<2<<std::endl;
if(max_index==0&&min_index>0&&min_index<=n-2)std::cout<<2<<std::endl;
if(max_index==0&&min_index==n-1)std::cout<<3<<std::endl;
if(min_index==n-1&&max_index>0&&max_index<=n-2)std::cout<<2<<std::endl;
}
return 0;
}
发表于 2020-09-12 11:49:07
回复(0)
#如果序列原本是有序的，就是0
#如果最后一个元素是最大值，只需要排序1次，直接输出1即可
#如果最后一个元素不是最大值，需要先排后n-1然后再排前n-1,直接输出2即可
#不用真的排序，判断情况直接输出0 1 2 就行
n = int(input())
a = list(map(int,input().split(' ')))if a == sorted(a):
print(0)
elif a[-1] == max(a):
print(1)
else:
print(2)
发表于 2020-09-06 17:50:31
回复(0)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] num=new int[n];
for(int i=0;i<n;i++){
num[i]=sc.nextInt();
}
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
if(num[i]<min){
min=num[i];
}
if(num[i]>max){
max=num[i];
}
}
if(min==num[0]||max==num[n-1]){
System.out.print(1);
}
if(min==num[n-1]&&max==num[0]){
System.out.print(3);
}
else{
System.out.print(2);
}
}
}
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] num=new int[n];
for(int i=0;i<n;i++){
num[i]=sc.nextInt();
}
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
if(num[i]<min){
min=num[i];
}
if(num[i]>max){
max=num[i];
}
}
if(min==num[0]||max==num[n-1]){
System.out.print(1);
}
if(min==num[n-1]&&max==num[0]){
System.out.print(3);
}
else{
System.out.print(2);
}
}
}
发表于 2020-08-23 11:31:25
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-13 08:14:23
-
2022-09-08 23:48:37 -
2022-09-08 18:47:31
-
2022-09-07 21:56:04 -
2022-09-07 06:11:55
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
