我们称一个长度为n的序列为正则序列,当且仅当该序列是一个由1~n组成的排列,即该序列由n个正整数组成,取值在[1,n]范围,且不存在重复的数,同时正则序列不要求排序
有一天小团得到了一个长度为n的任意序列s,他需要在有限次操作内,将这个序列变成一个正则序列,每次操作他可以任选序列中的一个数字,并将该数字加一或者减一。
请问他最少用多少次操作可以把这个序列变成正则序列?
数据范围:
,
进阶:时间复杂度
,空间复杂度![](https://www.nowcoder.com/equation?tex=O(n)%5C)
我们称一个长度为n的序列为正则序列,当且仅当该序列是一个由1~n组成的排列,即该序列由n个正整数组成,取值在[1,n]范围,且不存在重复的数,同时正则序列不要求排序
有一天小团得到了一个长度为n的任意序列s,他需要在有限次操作内,将这个序列变成一个正则序列,每次操作他可以任选序列中的一个数字,并将该数字加一或者减一。
输入第一行仅包含一个正整数n,表示任意序列的长度。(1<=n<=20000)
输入第二行包含n个整数,表示给出的序列,每个数的绝对值都小于10000。
输出仅包含一个整数,表示最少的操作数量。
5 -1 2 3 10 100
103
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; 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[] strSeq = br.readLine().trim().split(" "); int[] seq = new int[n]; for(int i = 0; i < n; i++) seq[i] = Integer.parseInt(strSeq[i]); Arrays.sort(seq); int modifyTimes = 0; for(int i = 1; i <= n; i++) modifyTimes += Math.abs(seq[i - 1] - i); System.out.println(modifyTimes); } }
#include <iostream> #include <vector> #include <algorithm> #include <stdlib.h> using namespace std; int main() { int n, ans = 0;; cin >> n; vector<int>que(n, 0); for (int i = 0; i < n; ++i) cin >> que[i]; sort(que.begin(), que.end()); for (int i = 1; i <= n; ++i) { ans += abs(i - que[i - 1]); } cout << ans; return 0; }
刚开始没看出来这道题目考的是什么?其实就是贪心。我们要让每个数字移动的步数最少,或者说让每个数字找距离下标[1,n]最近的位置填充。当时思路是有了,但是我一直没有排序,所以测试样例通过了,然后整体运行通不过,百思不得解。后来发现先排序,然后将所有数字按照[1,n]
的坑位从小到大填。这样就能保证距离最小,整体思路是对的,还要保证数组整体有序。
保证最后所有的数值取值在[1,n],先排序,然后从左到右遍历,这样就能取得最小步数。
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(); } Arrays.sort(arr); int res = 0; for(int j=1;j<=n;j++){ res += Math.abs(arr[j-1] - j); } System.out.println(res); } }
以上,下课
n = int(input()) a = list(map(int, input().strip().split())) a.sort() sum = 0 for i in range(1,n+1): sum += abs(i-a[i-1]) print(sum)
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; int ans = 0; for(int i = 0;i < n;i++) nums[i] = sc.nextInt(); Arrays.sort(nums); for(int i = 0;i < n;i++){ ans += Math.abs(i + 1 - nums[i]); } System.out.println(ans); } }
#include<iostream> using namespace std; const int N = 2e4 + 5; int n; int a[N], tmp[N]; int main() { cin >> n; int _max = 0; for (int i = 1; i <= n; i ++ ) { cin >> a[i]; tmp[a[i] + 10000]++; _max = max(_max, a[i] + 10000); } int idx = 0; for (int i = 0; i <= _max; i ++ ) { if (!tmp[i]) { continue; } while (tmp[i] -- > 0) { a[idx ++ ] = i - 10000; } } int ans = 0; for (int i = 1; i <= n; i ++ ) { ans += abs(i - a[i - 1]); } cout << ans << endl; return 0; }
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); for(int i = 0; i < n; i++) cin >> nums[i]; int count = 0; sort(nums.begin(), nums.end()); for(int i = 0; i < n; i++) { if(nums[i] >= 1 && nums[i] <= n) swap(nums[i], nums[nums[i] - 1]); } for(int i = 1; i <= n; i++) { if(i != nums[i - 1]) count += abs(nums[i - 1] - i); } cout << count << endl; return 0; }
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { int minCount = new Main().minCount(); System.out.println(minCount); } public int minCount(){ Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int[] arr=new int[n]; for(int i=0;i<n;i++) arr[i]=scanner.nextInt(); Arrays.sort(arr); int res=0; for(int i=0;i<n;i++){ res+=Math.abs(arr[i]-(i+1)); } return res; } }
#include<iostream> using namespace std; int main(){ int n; cin >> n; int b[20001] = {0}; for (int i = 0, num; i < n; i++) { cin >> num; b[num + 10000]++; } int ans = 0; for (int num = 0, j = 1; num < 20001 && j <= n; num++) { while (b[num]--) { ans += abs(j++ - num + 10000); } } cout << ans; return 0; }
package main import ( "fmt" "sort" ) func S(nums []int)int{ sort.Ints(nums) res:=0 n:=len(nums) var less,more []int myMap:=make(map[int]int,n) for i:=0;i<n;i++ { //把随意序列存进map并记录有多少个重复 myMap[nums[i]] += 1 } for i:=1;i<=len(nums);i++{ //循环正则序列的值,与随意序列比较有无多或少元素,多存进more,少存进less v,ok:=myMap[i] if nums[i-1]<1||nums[i-1]>=n+1{ //注意把超过n范围的元素加入more more=append(more,nums[i-1]) } if ok{ if v>1{ add(&more,v-1,i) continue } continue } less=append(less,i) } for i:=len(more)-1;i>=0;i--{ //此时more和less已经排序浩,长度相等,逐个相减累加和,就是结果 if more[i]>less[i]{ res+=more[i]-less[i] }else{ res+=less[i]-more[i] } } return res } func add(a *[]int, b,c int){ for i:=1;i<=b;i++{ *a=append(*a,c) } } func main(){ var n int fmt.Scan(&n) nums:=make([]int,n) for i:=0;i<n;i++{ fmt.Scan(&nums[i]) } res:=S(nums) fmt.Println(res) }
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[] arr1=new int[n]; int[] arr2=new int[n]; for (int i = 0; i < n; i++) { arr1[i]=i+1; arr2[i]=sc.nextInt(); } Arrays.sort(arr2); int sum=0; for (int i = 0; i < n; i++) { arr1[i]=Math.abs(arr1[i]-arr2[i]); sum+=arr1[i]; } System.out.println(sum); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int[] arr = new int[n]; int res = 0; for(int i = 0;i<n;i++){ arr[i] = s.nextInt(); } Arrays.sort(arr); while(arr[0] < 1){ arr[0]++; res++; } for(int i = 1;i<n;i++){ while(arr[i] <= arr[i-1]){ arr[i]++; res++; } } System.out.println(res); } }
#include <iostream> #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int t = 0; int count = 0; vector<int> hash(n + 1,0); for (int i = 0; i < n; i++) { cin >> t; if (t >= 1 && t <= n) { hash[t]++; } else if (t < 1) { count = count + 1 - t; hash[1]++; } else if (t > n) { count = count + t - n; hash[n]++; } } int sum = 0; for(int i=1;i<=n;i++) { sum = sum + hash[i] * i; } count = count + (1+n)*n/2 - sum; cout << count ; }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int ans = 0; int[] a = new int[n + 1]; for (int i = 0; i < n; i++) { int k = in.nextInt(); if (k < 1) { ans += 1 - k; a[1]++; } else if (k > n) { ans += k - n; a[n]++; } else { a[k]++; } } int x = 1; for (int i = 0; i <= n; i++) { while (a[i] > 1) { while (a[x] != 0) x++; ans += Math.abs(i - x); a[i]--; a[x]++; } } System.out.println(ans); } }
import java.util.Scanner; import java.lang.Math; // 贪心算法:对序列 s 进行排序,第 i 位通过加减乘除变成 i // 优化:采用桶排序 public class Main { public static void main(String[] args) { // value 映射到 value+10000 上 int[] buckets = new int[20001]; // 输入数组,放入桶中 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); while (n-- > 0) { ++buckets[scanner.nextInt()+10000]; } // 第 i 位通过加减乘除变成 i int result = 0, i = 1; for (int j = 0; j <= 20000; ++j) { while (buckets[j]-- > 0) { result += Math.abs((j-10000) - (i++)); } } System.out.println(result); } }