Cracking Coding Interview - 16.16 Sub Sort

Sub Sort: Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).

1
2
3


EXAMPLE
Input : 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19
Output: (3, 9)

Hints: #482, #553, #667, #708, #735, #746

解法

先观察例子：

1
2
3
4



1, 2, 4, [7, 10, 11, 7, 12, 6, 7], 16, 18, 19 
      ^                            ^
   左侧最大值                     右侧最小值

观察发现：

区间左边是有序的
区间右边是有序的
区间里的最小值大于左边的最大值
区间里的最大值小于右边的最小值

这个问题肯定不是排序问题，也不可能让你试遍所有可能性来找这个最小区间。

先来看怎么找m：

从左侧开始遍历，只要当前元素比前一个元素大，那么说明在升序中
当碰到当前元素 < 前一个元素小时，意味着遇到了降序，此时就要开始找之后遇到的最小元素是什么
遍历结束之后，再找这个最小元素应该插入到哪个位置，即第一个比它大的数所在的位置，这个位置就是m

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


                  开始降序
                    v
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19

                        找到min
                           v
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19

      这里就是m
         v
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19

再来看怎么找n：

从右侧开始找，只要当前元素比后一个元素小，说明在降序中
当碰到当前元素 > 前一个元素时，意味着遇到了升序，此时就要开始找之后遇到的最大的元素是什么
遍历结束之后，找这个最大元素应该插入到哪个位置，即第一个比它小的数所在的位置，这个位置就是n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


                    开始升序
                       v
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19

                     找到max
                       v
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19

                           这里就是n
                              v
1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


public void subSort(int[] nums) {
  int m = find_m(nums);
  if (m == -1) {
    System.out.println("already sorted");
    return;
  }
  int n = find_n(nums);
  System.out.println("m: " + m + ", n: " + n);
}

public int find_m(int[] nums) {
  Integer min = null;
  for (int i = 1; i < nums.length, i++) {
    if (nums[i] < nums[i - 1]) {
      min = findMin(nums, i, nums.length - 1);
      break;
    }
  }
  if (min == null) {
    return -1;
  }
  return findFirstGtIndex(nums, min);
}

private int findMin(int[] nums, int start, int end) {
  int min = nums[start];
  for (int i = start + 1; i <= end; i++) {
    if (nums[i] < min) {
      min = nums[i];
    }
  }
  return min;
}

private int findFirstGtIndex(int[] nums, int a) {
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] > a) {
      return i;
    }
  }
  return -1;
}

public int find_n(int[] nums) {
  Integer max = null;
  for (int i = nums.length - 2; i >= 0; i--) {
    if (nums[i] > nums[i + 1]) {
      max = findMax(nums, i, 0);
      break;
    }
  }
  if (max == null) {
    return -1;
  }
  return findFirstLt(nums, max);
}

private int findMax(int[] nums, int end, int start) {
  int max = nums[end];
  for (int i = end - 1; i >= start; i++) {
    if (nums[i] > max) {
      max = nums[i];
    }
  }
  return max;
}

private int findFirstLt(int[] nums, int a) {
  for (int i = nums.length - 1; i >= 0; i--) {
    if (nums[i] < a) {
      return i;
    }
  }
  return -1;
}

Cracking Coding Interview - 16.16 Sub Sort

解法

版权

评论

Cracking Coding Interview - 16.16 Sub Sort

解法

版权

相关文章

评论