バージョン番号の並べ替え

Question

以下のコードは、バージョン番号を正しい順序で並べ替えるものです。ほとんどの場合、動作しますが、アクセスできない隠れたテストケースには失敗します。それは私が行方不明かもしれないことがわかることができるエッジケースがあることを考える。こうした2や2.0などバージョン番号が生じたときのために意味

specialCompare方法上記のコード内のコメントから、

import java.util.*; 

public class Answer { 
public static void main(String[] args) 
{ 
    //Testing 
    String[] versions = {"0.0.0","0","0.0","1.113","0.0.0.1","2.0.0","1.2","2","0.1","1.2.1","1.1.1","2.0"}; 
    String[] results = answer(versions); 
    for(int i =0; i<results.length;i++) 
    { 
     System.out.println(results[i]); 
    } 
} 
public static String[] answer(String[] l) { 

    String temp = new String(); 
    //Insertion sort on the given array to assign correct version numbers 
    for (int i = 1; i < l.length; i++) { 
     for(int j = i ; j > 0 ; j--){ 
      if(compareVersion(l[j],l[j-1])<0){ 
       temp = l[j]; 
       l[j] = l[j-1]; 
       l[j-1] = temp; 
      } 
     } 
    } 
    return l; 
} 
//Will compare version numbers breaking it apart into a String array 
public static int compareVersion(String version1, String version2) { 
String[] arr1 = version1.split("\\."); 
String[] arr2 = version2.split("\\."); 

int i=0; 
while(i<arr1.length || i<arr2.length){ 
    if(i<arr1.length && i<arr2.length){ 
     if(Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])){ 
      return -1; 
     }else if(Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])){ 
      return 1; 
     } 
     else if(Integer.parseInt(arr1[i]) == Integer.parseInt(arr2[i])) 
     { 
      int result = specialCompare(version1,version2); 
      if(result != 0) 
      { 
       return result; 
      } 
     } 
    } else if(i<arr1.length){ 
     if(Integer.parseInt(arr1[i]) != 0){ 
      return 1; 
     } 
    } else if(i<arr2.length){ 
     if(Integer.parseInt(arr2[i]) != 0){ 
      return -1; 
     } 
    } 

    i++; 
} 

return 0; 
} 
    // Meant for when version numbers such as 2 and 2.0 arise. This method will make sure to 
    // put the smaller version number (in length) first 
    public static int specialCompare(String str1, String str2) 
{ 
     String[] arr1 = str1.split("\\."); 
    String[] arr2 = str2.split("\\."); 
    for(int i =1; i<arr1.length;i++) 
    { 
     if(Integer.parseInt(arr1[i]) != 0) 
     { 
      return 0; 
     } 
    } 
    for(int j =1; j<arr2.length;j++) 
    { 
     if(Integer.parseInt(arr2[j]) != 0) 
     { 
      return 0; 
     } 
    } 
    if(arr1.length < arr2.length) 
    { 
     return -1; 
    } 
    else 
    { 
     return 1; 
    } 

} 
} 

Answer 1

...

。この方法 は、だから私はあなたがバージョンはバージョン番号の長さでソートしたいことをこのことから推測しています最初の

を（長さ）小さいバージョン番号を入れて確認します。例：あなたの供給バージョンの文字列配列から、あなたが以下のようにソートしたい...

0 
2 
0.0 
0.1 
1.2 
1.113 
2.0 
0.0.0 
1.1.1 
1.2.1 
2.0.0 
0.0.0.1 

このような場合は、その後、あなたはそれがために持っているよりも、これはより複雑になっているようです。バージョンの長さが異なる2つのバージョンを取得すると、バージョンの長さが短いものが最初に表示されます。したがって、バージョン分割配列の長さを簡単にチェックすれば、これを解決するはずです。同じ長さの場合は、各バージョンを確認する必要があります。バージョンの長さが同じ場合は、specialCompareメソッドは必要ありません。単に各バージョンを確認し、それらが同じであれば、次のバージョン番号などに進みます。 1つのバージョンが異なると、すぐに何を返すかが分かります。配列全体を見ると、すべてのバージョン番号が同じであることがわかります。

以下は、上記のロジックを使用してcompareVersionメソッドに変更したものです。 specialCompareメソッドは必要ありません。私はこれがあなたが探しているものだと推測しています。

public static int compareVersion(String version1, String version2) 
{ 
    String[] arr1 = version1.split("\\."); 
    String[] arr2 = version2.split("\\."); 

    if (arr1.length < arr2.length) 
    return -1; 
    if (arr1.length > arr2.length) 
    return 1; 

    // same number of version "." dots 
    for (int i = 0; i < arr1.length; i++) 
    { 
    if(Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])) 
     return -1; 
    if(Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])) 
     return 1; 
    } 
    // went through all version numbers and they are all the same 
    return 0; 
} 

Answer 2

package com.e;

import java.util。*;

/** * 17-2-27のdpcで作成されます。 * */ パブリッククラスVersionComparatorは、コンパレータを実装{

@Override 
public int compare(String o1, String o2) { 

    if (o1 == null && o2 == null) { 
     return 0; 
    } else if (o1 == null && o2 != null) { 
     return -1; 
    } else if (o1 != null && o2 == null) { 
     return 1; 
    } else { 
     if (o1.length() == 0 && o2.length() == 0) { 
      return 0; 
     } else if (o1.length() == 0 && o2.length() > 0) { 
      return -1; 
     } else if (o1.length() > 0 && o2.length() == 0) { 
      return 1; 
     } else { 
      return compareVersion(o1, o2); 
     } 
    } 


} 


public static int compareVersion(String version1, String version2) { 
    String[] arr1 = version1.split("\\."); 
    String[] arr2 = version2.split("\\."); 

    try { 

     int i = 0; 
     while (i < arr1.length || i < arr2.length) { 
      if (i < arr1.length && i < arr2.length) { 
       if (Integer.parseInt(arr1[i]) < Integer.parseInt(arr2[i])) { 
        return -1; 
       } else if (Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])) { 
        return 1; 
       } else if (Integer.parseInt(arr1[i]) == Integer.parseInt(arr2[i])) { 
        int result = specialCompare(version1, version2); 
        if (result != 0) { 
         return result; 
        } 
       } 
      } else if (i < arr1.length) { 
       if (Integer.parseInt(arr1[i]) != 0) { 
        return 1; 
       } 
      } else if (i < arr2.length) { 
       if (Integer.parseInt(arr2[i]) != 0) { 
        return -1; 
       } 
      } 

      i++; 
     } 
    } catch (Exception e) { 
     e.printStackTrace(); 
    } 
    return 0; 
} 

public static int specialCompare(String str1, String str2) { 
    String[] arr1 = str1.split("\\."); 
    String[] arr2 = str2.split("\\."); 
    for (int i = 1; i < arr1.length; i++) { 
     if (Integer.parseInt(arr1[i]) != 0) { 
      return 0; 
     } 
    } 
    for (int j = 1; j < arr2.length; j++) { 
     if (Integer.parseInt(arr2[j]) != 0) { 
      return 0; 
     } 
    } 
    if (arr1.length < arr2.length) { 
     return -1; 
    } else { 
     return 1; 
    } 
} 


// test 
public static List<String> getLowerList(String str, Comparator<String> comparator, List<String> list) { 
    if (str == null) { 
     return list; 
    } 
    List<String> newlist = new ArrayList<String>(); 
    newlist.add(str); 
    newlist.addAll(list); 
    // sort 
    Collections.sort(newlist, comparator); 
    // search 
    int endIndex = Collections.binarySearch(newlist, str); 
    if (endIndex >= 0) { 
     // sublist 0 1 
     return newlist.subList(0, endIndex + 1); 
    } else { 
     return new ArrayList<String>(); 
    } 
} 

public static void main(String[] args) { 
    List<String> test1 = Arrays.asList(new String[]{ 
      "2.1.1", "1.21.22", "1.21.25", "1.113", "0.0.0.1", 
      "2.0.0", "1.2", "2.0", "0.1", "1.2.1", "1.1.1", 
      "11", "100", "" + Integer.MAX_VALUE + ".1", "", 
      "2.0", "10.1"}); 

    List<String> test2 = Arrays.asList(new String[]{"", null, "0", "10.20.100", "3.1.1", "9.8", "10.3.92"}); 

    List<String> newlist = new ArrayList<String>(); 
    newlist.addAll(test1); 
    newlist.addAll(test2); 

    Collections.sort(newlist, new VersionComparator()); 

    VersionComparator compareVersion = new VersionComparator(); 
    System.out.println(newlist); 

    System.out.println(getLowerList("2", compareVersion, newlist)); 
    System.out.println(getLowerList("3", compareVersion, newlist)); 
    System.out.println(getLowerList("4", compareVersion, newlist)); 
    System.out.println(getLowerList("5", compareVersion, newlist)); 

} 

}

Answer 3

私は最近、Windowsのエクスプローラでファイルをソートする方法に似て、任意のファイル名には、より一般的な方法でこれを行う必要性を、持っていました：

I wrote a blog post about this。 The idea was inspired by this answer here。

public final class FilenameComparator implements Comparator<String> { 
    private static final Pattern NUMBERS = 
     Pattern.compile("(?<=\\D)(?=\\d)|(?<=\\d)(?=\\D)"); 
    @Override public final int compare(String o1, String o2) { 
     // Optional "NULLS LAST" semantics: 
     if (o1 == null || o2 == null) 
      return o1 == null ? o2 == null ? 0 : -1 : 1; 

     // Splitting both input strings by the above patterns 
     String[] split1 = NUMBERS.split(o1); 
     String[] split2 = NUMBERS.split(o2); 
     for (int i = 0; i < Math.min(split1.length, split2.length); i++) { 
      char c1 = split1[i].charAt(0); 
      char c2 = split2[i].charAt(0); 
      int cmp = 0; 

      // If both segments start with a digit, sort them numerically using 
      // BigInteger to stay safe 
      if (c1 >= '0' && c1 <= '9' && c2 >= 0 && c2 <= '9') 
       cmp = new BigInteger(split1[i]).compareTo(new BigInteger(split2[i])); 

      // If we haven't sorted numerically before, or if numeric sorting yielded 
      // equality (e.g 007 and 7) then sort lexicographically 
      if (cmp == 0) 
       cmp = split1[i].compareTo(split2[i]); 

      // Abort once some prefix has unequal ordering 
      if (cmp != 0) 
       return cmp; 
     } 

     // If we reach this, then both strings have equally ordered prefixes, but 
     // maybe one string is longer than the other (i.e. has more segments) 
     return split1.length - split2.length; 
    } 
}