We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Larry's Array
  5. Discussions

Larry's Array

  • duy_pham2508
     + 0 comments

    I think this problem can be solved by finding the smallest number of swaps so that it becomes an increasing chain, but this number of swaps must be divisible by 2 because in this lesson, each time you swap, you have to swap consecutively. swap 2 times in a row and if those times are numbers that are not divisible by 2 then it will be incorrect because in 1 swap you cannot swap 3 times in a row in 1 time.

              int count = 0 ;                    
        int n = A.size() ;  
        List<Integer> tempArr  = new ArrayList<>(A) ; 
        List<Integer> sorted =  new ArrayList<>(A) ; 
        Map<Integer, Integer> indexMap = new LinkedHashMap<>() ; 
        for(int i = 0; i < n ; i++ ) {
            indexMap.put(A.get(i),i) ;  
        }         
        Collections.sort(sorted) ; 
        
        
         for(int i = 0 ; i < n ; i++ ) { 
            if(tempArr.get(i) != sorted.get(i)) {
                count ++ ;  
                int newValue = tempArr.get(i) ;  
                int newIndex = indexMap.get(sorted.get(i)) ;   
                indexMap.put(newValue, newIndex); 
                Collections.swap(tempArr, i, indexMap.get(sorted.get(i)));                 
                indexMap.put(sorted.get(i), i);
            }
        }
        if(count %2 == 0) {
            return "YES" ; 
        }
        else {
            return "NO" ; 
        }