"Coding Interview Guide" -- 数组的partition调整

时间：2022-10-13 19:56:41

【题目】

　　给定一个有序数组arr，调整arr使得这个数组的左半部分没有重复元素且升序，而不用保证右部分是否有序

　　例如，arr=[1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9]，调整之后arr=[1, 2, 3, 4, 5, 6, 7, 8 ,9, ...]

 

【要求】

　　时间复杂度为O(N)，额外空间复杂度为O(1)

 

 1 public void leftUniqueSort(int[] arr)
 2 {
 3     if(arr == null || arr.length < 2)
 4     {
 5     return;
 6     }
 7 
 8     int left = 0;
 9     int cur = 1;
10         
11     while(cur != arr.length)
12     {
13     if(arr[cur] != arr[left])
14     {
15         swap(arr, ++left, cur);
16     }
17     cur++;
18     }
19 }

 

 

【题目】

　　给定一个数组arr，其中只可能含有0、1、2三个值，请实现arr的排序

 

【要求】

　　时间复杂度为O(N)，额外空间复杂度为O(1)

 1 public void sort(int[] arr)
 2 {
 3     if(arr == null || arr.length < 2)
 4     {
 5     return;
 6     }
 7 
 8     int left = -1;
 9     int index = 0;
10     int right = arr.length;
11         
12     while(index < right)
13     {
14     if(arr[index] == 0)
15     {
16         swap(arr, ++left, index++);
17     }
18     else if(arr[index] == 2)
19     {
20          swap(arr, index, --right);
21     }
22     else
23     {
24         index++;
25     }
26     }
27 }

 

 

【题目】

　　有一个数组arr，给定一个值k，实现比k小的数都放在数组的左边，等于k的数都放在数组的中间，大于k的数都放在数组的右边

 

【要求】

　　时间复杂度为O(N)，额外空间复杂度为O(1)

 1 public void sort(int[] arr, int k)
 2 {
 3     if(arr == null || arr.length < 2)
 4     {
 5     return;
 6     }
 7 
 8     int left = -1;
 9     int index = 0;
10     int right = arr.length;
11         
12     while(index < right)
13     {
14     if(arr[index] < k)
15     {
16         swap(arr, ++left, index++);
17     }
18     else if(arr[index] > k)
19     {
20         swap(arr, index, --right);
21     }
22     else
23     {
24         index++;
25     }
26     }
27 }

 

1 public void swap(int[] arr, int i, int j)
2 {
3     int temp = arr[i];
4     arr[i] = arr[j];
5     arr[j] = temp;
6 }

 

来源：左程云老师《程序员代码面试指南》

标签：

相关文章