首页 > 代码库 > Coursera Algorithms week2 基础排序 Interview Questions: 2 Permutation
Coursera Algorithms week2 基础排序 Interview Questions: 2 Permutation
题目原文:
Given two integer arrays of size n , design a subquadratic algorithm to determine whether one is a permutation of the other. That is, do they contain exactly the same entries but, possibly, in a different order.
本质上就是求两个数组排序后是否相等,鉴于本节课学的是选择、插入、希尔排序,就选个最不熟悉的希尔排序来实现吧
1 import java.util.Arrays; 2 3 public class PermutationArrays { 4 private int[] a; 5 private int[] b; 6 private int n; 7 PermutationArrays(int n, int[] a, int[] b){ 8 this.a = a; 9 this.b = b; 10 this.n = n; 11 } 12 private boolean less(int v, int w){ 13 return v < w; 14 } 15 private void exch(int[] a, int i, int j){ 16 int t = a[i]; 17 a[i] = a[j]; 18 a[j] = t; 19 } 20 private void sortByShell(int n, int[] a){ 21 int h = 1; 22 while(h < n/3){ 23 h = 3*h + 1; 24 } 25 while(h>=1){ 26 for(int i = h; i<n;i++){ 27 for(int j = i; j>=h && less(a[j],a[j-h]);j=j-h){ 28 exch(a,j,j-h); 29 } 30 } 31 h = h/3; 32 } 33 } 34 public boolean isPermutation(){ 35 sortByShell(n,a); 36 System.out.println(Arrays.toString(a)); 37 sortByShell(n,b); 38 System.out.println(Arrays.toString(b)); 39 for(int i=0;i<n;i++){ 40 if(a[i] != b[i]) 41 return false; 42 } 43 return true; 44 } 45 public static void main(String[] args){ 46 int[] a = {1,2,4,5,6,11,9,7,8,0}; 47 int[] b = {0,9,8,7,6,5,4,3,2,1}; 48 PermutationArrays pa = new PermutationArrays(10,a,b); 49 System.out.println(pa.isPermutation()); 50 } 51 }
Coursera Algorithms week2 基础排序 Interview Questions: 2 Permutation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。