625.配列区分II

2973 ワード

説明
ソートされていない整数配列を3つの部分に分割します:1.第1部のすべての値は=lowであり、<=high 3である.第3部のすべての値は、>highが任意の可能な場合を返します.
注意事項
すべてのテスト配列にlow<=highがある.
サンプル
配列[4,3,4,1,2,3,1,2],low=2,high=3が与えられる.[1,1,2,3,2,3,4,4]になります([1,1,2,2,3,3,4,4]も正解ですが[1,2,1,2,2,3,4,4]ではありません)
に挑戦
1.その場で2.1サイクルで完了
に注意
分割配列が状況に等しくなくても均等に分割される限り、while判断でleft==rightの状況を考慮する必要はありません.分割時に分割参照値が配列に存在するかどうかも考慮しなければならないので、存在しない場合は境界状況を考慮しなければなりません.

コード#コード#

  • 2 2本のポインタ
  • public class Solution {
        /**
         * @param nums an integer array
         * @param low an integer
         * @param high an integer
         * @return nothing
         */
        public void partition2(int[] nums, int low, int high) {
            // Write your code here
            if (nums == null || nums.length <= 1) {
                return;
            }
            
            int pl = 0, pr = nums.length - 1;
            int i = 0;
            while (i <= pr) {
                if (nums[i] < low) {
                    swap(nums, pl, i);
                    pl++;
                    //   low  ,  high  ,
                    //   low,  low,  i++
                    i++;
                } else if (nums[i] > high) {
                    swap(nums, pr, i);
                    pr--;
                } else {
                    i ++;
                }
            }
        }
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    
  • 2 2分割
  • public class Solution {
        /**
         * @param nums an integer array
         * @param low an integer
         * @param high an integer
         * @return nothing
         */
        public void partition2(int[] nums, int low, int high) {
            // Write your code here
            int left = 0;
            int right = nums.length - 1;
    
            //   < low   >= low   
            while(left <= right) {
                while(left <= right && nums[left] < low) {
                    left ++;
                }
                while(left <= right && nums[right] >= low) {
                    right --;
                }
    
                if(left <= right) {
                    int tmp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = tmp;
                    left ++;
                    right --;
                }
            }
    
            //  left low 
            //   >= low   <= high   > high  
            right = nums.length - 1;
            while(left <= right) {
                while(left <= right && nums[left] <= high) {
                    left ++;
                }
                while(left <= right && nums[right] > high) {
                    right --;
                }
                if(left <= right) {
                    int tmp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = tmp;
                    left ++;
                    right --;
                }
            }
        }
    }