如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。
小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列
[编程题]等差数列
时间复杂度为n的方案。
import java.util.HashSet;
import java.util.Scanner;
/**
* @Author: coderjjp
* @Date: 2020-05-13 16:53
* @Description: 等差数列
* @version: 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int num[] = new int[n];
int min = 0, max = 1000;
for (int i = 0; i < n; i++){
num[i] = sc.nextInt();
if (num[i] < min)
min = num[i];
if (num[i] > max)
max = num[i];
}
if (max == min){
System.out.println("Possible");
return;
}
if ((max - min) % (n - 1) != 0){
System.out.println("Impossible");
return;
}
int dis = (max - min) / (n - 1);
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++){
if (!set.add(num[i] - dis)){
System.out.println("Impossible");
return;
}
}
System.out.println("Possible");
}
}
发表于 2020-05-13 17:20:16
回复(0)
- 先进行排序
- 把arr[0]-arr[1]作为公差d，然后遍历数组找反例，如果存在公差不等的情况就终止循环，说明不是等差数列
- 如果遍历完整个数组还找不到反例，说明就是等差数列
import java.util.*;
public class Main
{
public static void main(String [] args)
{
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt())
{
int n=sc.nextInt();
int [] arr=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
Arrays.sort(arr);
int d=arr[0]-arr[1];//公差
boolean flag=true;
for(int i=1;i<arr.length-1;i++)
{
int cur=arr[i]-arr[i+1];
if(cur!=d)
{
flag=false;
System.out.println("Impossible");
break;
}
}
if(flag)
{
System.out.println("Possible");
}
}
}
}
发表于 2020-03-29 11:09:33
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arr = new int[num];
for(int i=0;i<num;i++){
arr[i] = sc.nextInt();
}
int d = 0;
for(int j=0;j<num;j++){
for(int k=j+1;k<num;k++){
if(arr[j] > arr[k]){
swap(arr,j,k);
}
}
if(1==j){
d = arr[1] - arr[0];
}else if(j>1){
int dl = arr[j] - arr[j-1];
if(d!=dl){
System.out.println("Impossible");
return;
}
}
}
System.out.println("Possible");
}
private static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arr = new int[num];
for(int i=0;i<num;i++){
arr[i] = sc.nextInt();
}
int d = 0;
for(int j=0;j<num;j++){
for(int k=j+1;k<num;k++){
if(arr[j] > arr[k]){
swap(arr,j,k);
}
}
if(1==j){
d = arr[1] - arr[0];
}else if(j>1){
int dl = arr[j] - arr[j-1];
if(d!=dl){
System.out.println("Impossible");
return;
}
}
}
System.out.println("Possible");
}
private static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
发表于 2019-11-25 22:22:38
回复(2)
首先需要排序，排序好了以后需要用到二分搜查的思路，为了省时间从两边开始判断，先定义一个d,d=数组里面的任何一个数减去它前面的数，然后从两边开始判断前后两个数的差是否跟d相等就完事儿了
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner (System.in);
int n=cin.nextInt();//数组长度;
int a[]=new int[n];
for(int i=0;i<n;i++) {
a[i]=cin.nextInt();
}
Arrays.sort(a);
int left=1;
int right=n-1;
int temp=a[1]-a[0];
int x=0;
while (left<=right) {
if(a[left]-a[left-1] !=temp || a[right]-a[right-1] !=temp) {
x=1;
break;
}
left++;
right--;
}
if(x==0)System.out.print("Possible");
else if(x==1)System.out.print("Impossible");
}
}
发表于 2019-11-04 16:22:01
回复(0)
import java.util.Scanner;
public class Main { public static Scanner scan = new Scanner(System.in); public static void main(String[] args) { int num = scan.nextInt(); int array[] = new int[num]; for (int i = 0; i < array.length; i++) { array[i] = scan.nextInt(); } for (int i = 0; i < array.length-1; i++) { for (int j = 0; j+1 < array.length-i; j++) { if(array[j]>array[j+1]) { int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } int a= array[1]-array[0]; int count=0; for (int i = 1; i < array.length-1; i++) { if(array[i+1]-array[i]==a) { count++; continue; } } if(count==num-2) { System.out.println("Possible"); }else { System.out.println("Impossible"); } }
}
发表于 2019-06-29 12:26:29
回复(0)
import java.util.Arrays;
import java.util.Scanner;
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();
}
Boolean flag = true;
if (n > 2) {
Arrays.sort(arr);
int num = arr[1] - arr[0];
for (int i = 2; i < arr.length; i++) {
if (arr[i] - arr[i - 1] != num) {
flag = false;
break;
}
}
}
if (flag) {
System.out.println("Possible");
} else {
System.out.println("Impossible");
}
}
}
发表于 2019-06-10 13:49:41
回复(0)
排序完之后，然后依次判断每个项是否都相差公差即可：
private static String solution(int[] arr) {
Arrays.sort(arr);
int d = arr[1] - arr[0]; // 公差
for (int i = 2; i < arr.length; i++) {
if (arr[i - 1] + d != arr[i]) {
return "Impossible";
}
}
return "Possible";
}
发表于 2019-05-08 14:18:53
回复(0)
思路比较简单，等差数列，肯定是从大到小或者从小到大，将输入的数组排序， 然后将排列的数组间俩俩互减，然后将互减结果与公差比较，是一致输出对应结果 importjava.util.Arrays; import java.util.Scanner; public class shulie { public static void main(String[] args){ Scanner s=new Scanner(System.in); int a=s.nextInt(); int [] b=new int[a]; for (int i=0;i<a;i++){ b[i]=s.nextInt(); } for (int i=0;i<a;i++){ for (int j=i;j<a;j++){ if (b[i]>b[j]){ int temp; temp=b[i]; b[i]=b[j]; b[j]=temp; } } } Boolean flag=true; Arrays.sort(b); int d=b[1]-b[0]; for (int j=2;j<b.length;j++){ if (b[j]-b[j-1]!=d){ flag=false; } } if (flag){ System.out.print("Possible"); } else{ System.out.print("Impossible"); } } }
编辑于 2019-04-22 15:34:35
回复(0)
import java.io.*;
import java.util.Arrays;
public class Main {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[]args)throws Exception {
int n=Integer.parseInt(br.readLine());
int []numArray=new int[n];
String []strArray=br.readLine().trim().split(" ");
for(int i=0;i<strArray.length;i++) {
numArray[i]=Integer.parseInt(strArray[i]);
}
Arrays.sort(numArray);
int d=0;
String result="Possible";
if(numArray.length>=2) {
d=numArray[1]-numArray[0];
for(int i=1;i<numArray.length;i++) {
if(numArray[i]-numArray[i-1]!=d) {
result="Impossible";
break;
}
}
}
System.out.println(result);
}
}
import java.util.Arrays;
public class Main {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[]args)throws Exception {
int n=Integer.parseInt(br.readLine());
int []numArray=new int[n];
String []strArray=br.readLine().trim().split(" ");
for(int i=0;i<strArray.length;i++) {
numArray[i]=Integer.parseInt(strArray[i]);
}
Arrays.sort(numArray);
int d=0;
String result="Possible";
if(numArray.length>=2) {
d=numArray[1]-numArray[0];
for(int i=1;i<numArray.length;i++) {
if(numArray[i]-numArray[i-1]!=d) {
result="Impossible";
break;
}
}
}
System.out.println(result);
}
}
发表于 2019-04-15 13:41:05
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
boolean isAP = IsArithmeticProgression(arr);
if(isAP) {
System.out.println("Possible");
}
else {
System.out.println("Impossible");
}
}
}
public static boolean IsArithmeticProgression(int[] arr) {
if(arr.length==1||arr.length==2) {
return true;
}
Arrays.sort(arr);
int d = arr[1] - arr[0];
for(int i = 2;i < arr.length; i++) {
int t = arr[i] - arr[i-1];
if(t!=d) {
return false;
}
}
return true;
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
boolean isAP = IsArithmeticProgression(arr);
if(isAP) {
System.out.println("Possible");
}
else {
System.out.println("Impossible");
}
}
}
public static boolean IsArithmeticProgression(int[] arr) {
if(arr.length==1||arr.length==2) {
return true;
}
Arrays.sort(arr);
int d = arr[1] - arr[0];
for(int i = 2;i < arr.length; i++) {
int t = arr[i] - arr[i-1];
if(t!=d) {
return false;
}
}
return true;
}
}
发表于 2019-04-05 15:17:25
回复(0)
import java.util.Scanner;
import java.util.Arrays;
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();
}
Arrays.sort(arr);
if (arr[1]-arr[0]!=arr[2]-arr[1]){
System.out.println("Impossible");
}
else{
System.out.println("Possible");
}
}
}
import java.util.Arrays;
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();
}
Arrays.sort(arr);
if (arr[1]-arr[0]!=arr[2]-arr[1]){
System.out.println("Impossible");
}
else{
System.out.println("Possible");
}
}
}
发表于 2019-03-24 20:54:09
回复(0)
思路：先获得最大、最小值，算出等差数列的d；用Map来存储每个出现数字的出现次数，查找时复杂度为o(1) import java.util.*; public class Main{ public static void main(String[] args){ Scanner input = new Scanner(System.in); int n = input.nextInt(); Map<integer> map = new HashMap<integer>(); int temp = input.nextInt(); map.put(temp,1); int max = temp, min = temp; for(int i=1;i<n>temp?temp:min; } int d = (max - min)/(n-1); for(int i=1;i</n></integer></integer>
发表于 2019-03-17 20:27:52
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a=sc.nextInt();
int n[] = new int[a];
for(int i=0;i<a;i++)
System.out.println("Possible");
System.out.println(k(n)?"Possible":"Impossible");
}
}
public static void sort(int a[]) {
int len=a.length;
int tmp;
for(int i=0;i<len;i++)
for(int j=i+1;j<len;j++) {
if(a[i]>a[j]) {
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
public static boolean k(int[]n) {
int len=n.length;
int h=n[1]-n[0];
for(int i=0;i<len-1;i++) {
if((n[i+1]-n[i])!=h)
return false;
}
return true;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a=sc.nextInt();
int n[] = new int[a];
for(int i=0;i<a;i++)
n[i] = sc.nextInt();
//如果数组长度为1或者为2，则为正确
if(a==1||a==2) {System.out.println("Possible");
}else {
//先对数组排序
sort(n);System.out.println(k(n)?"Possible":"Impossible");
}
}
public static void sort(int a[]) {
int len=a.length;
int tmp;
for(int i=0;i<len;i++)
for(int j=i+1;j<len;j++) {
if(a[i]>a[j]) {
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
}
//已排好序的数组，判断后一项与前一项的差是否恒为常数
int len=n.length;
int h=n[1]-n[0];
for(int i=0;i<len-1;i++) {
if((n[i+1]-n[i])!=h)
return false;
}
return true;
}
}
发表于 2019-03-13 21:38:54
回复(0)
import java.util.Scanner;
import static java.util.Arrays.sort;
public class DengChaShuLie {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int min = 1001;
int sum = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
sum+=arr[i];
if (arr[i] < min) {
min = arr[i];
}
}
int d = (sum-nmin)2/(n*(n-1));
sort(arr);
int i;
for (i = 0; i < n; i++) {
if (arr[i] != min + d * i) {
System.out.println("Impossible");
break;
}
}
if (i == n) {
System.out.println("Possible");
}
}
}
发表于 2019-03-10 19:38:24
回复(0)
/*将数组用array.sort()方法排序，d=等于a[0]-a[1]的绝对值，然后遍历依次判断d是否等于a[i]-a[+1]的绝对值，不等则输出Impossible，并return,遍历结束后，输出Possible
*/
import java.util.Arrays;
import java.util.Scanner;public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
Arrays.sort(array);
int flag=Math.abs(array[0]-array[1]);
for(int i=0;i<array.length-1;i++) {
if(flag!=Math.abs(array[i]-array[i+1])){
System.out.println("impossible");
return ;
}
}
System.out.println("possible");
}
}
发表于 2019-03-02 13:44:35
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void result(int[] m){
Arrays.sort(m);
int d=m[1]-m[0];
int count=0;
for (int i = 0; i length-1; i++) {
if (m[i+1]==m[i]+d){
count++;
}
}
if (count==m.length-1){
System.out.println("Possible");
}else
System.out.println("Impossible");
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int[] m=new int[n];
for (int i = 0; i ; i++) {
m[i]=scanner.nextInt(); }
Main.result(m); }
}
编辑于 2019-02-22 15:12:09
回复(1)
import java.util.*;
public class Main{
public static void main(String[] args){
try(Scanner in = new Scanner(System.in)){
int n = Integer.parseInt(in.nextLine()),i = 0;
int[] a = new int[n];
while(in.hasNextInt()){
a[i++] = in.nextInt();
}
System.out.println(helper(a));
}
}
public static String helper(int[] a){
Arrays.sort(a);
int d = a[1] - a[0],i = 2;
while(i < a.length){
if(a[i] - a[i - 1] != d) return "Impossible";
i++;
}
return "Possible";
}
}
发表于 2019-01-12 14:02:06
回复(0)
//输入一个数字表示数组的长度，再依次输入数组的每一个元素，采纳率最高的那个答案不全面，在测试用例的通过率只有80％
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int[] arr = new int[num];
for(int i = 0; i < num ;i++){
arr[i] = in.nextInt();
}
Arrays.sort(arr);
//需要定义一个布尔变量标记是否成功
boolean flag = true;
int d = arr[1] - arr[0];
for(int i = 2;i<arr.length;i++){
if(arr[i] - arr[i-1] != d){
flag = false;
}
}
if(flag){
System.out.println("Possible");
}else{
System.out.println("Impossible");
}
}
}
发表于 2017-08-31 16:02:27
回复(5)
问题信息
通过挑战的用户
查看代码-
2022-10-07 00:54:09 -
2022-09-08 20:54:32
-
2022-09-03 21:11:56
-
2022-09-03 15:24:27
-
2022-08-30 23:10:02
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
