# 算法细节系列（35）：不一样的排序

## Leetcode 215. Kth Largest Element in an Array

```nums = {5,1,3,2,4,9,6,7,8};

{1,3,2,4} 5 {9,6,7,8}

```    public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}

private int partition(int[] a, int lo, int hi) {

int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && a[++i] < a[lo]);
while(j > lo && a[--j] > a[lo]);
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}

private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}```

## Leetcode 324. Wiggle Sort II

```    public void wiggleSort(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int[] aux = new int[n];
for (int i = ((n - 1) % 2 == 0 ? n - 1 : n - 2), k = 0; i >= 0; i -= 2){
aux[i] = nums[k++];
}
for (int i = 1, k = n - 1; i < n; i += 2){
aux[i] = nums[k--];
}
for (int i = 0; i < n; i++){
nums[i] = aux[i];
}
}```

```private int map(int i, int n){
return (1 + 2 * i) % (n | 1);
}

n | 1其实是一种结合判断条件和赋值于一身的代码小技巧，实际含义：
if n % 2 == 0; n = n + 1;
if n % 2 != 0; n = n;

map映射的效果是：

n为偶数的情况：
origin : 0 1 2 3 4 5 6 7 8 9
new    : 1 3 5 7 9 2 4 6 8 10

n为奇数的情况：
origin : 0 1 2 3 4 5 6 7 8
new    : 1 3 5 7 2 4 6 8 10```

num与中位数相等怎么办？很有趣，因为在放入奇数坑和偶数坑是交错开来的，所以遇到中位数的情况放在原位置就好了，而不会出现两中位数在一块的情况。

```public void wiggleSort(int[] nums) {
int n = nums.length;
int median = findKthLargest(nums, (nums.length + 1) / 2);
int i = 0, lf = 0, rt = n - 1;
while (i <= rt){
if (nums[map(i,n)] > median){
exch(nums, map(lf++, n), map(i++,n));
}
else if (nums[map(i, n)] < median){
exch(nums, map(rt--, n), map(i, n));
}
else{
i++;
}
}
}

private int map(int i, int n){
return (1 + 2 * i) % (n | 1);
}

public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}

private int partition(int[] a, int lo, int hi) {

int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && a[++i] < a[lo]);
while(j > lo && a[--j] > a[lo]);
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}

private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}```

## Leetcode 179. Largest Number

• 长度相同的number，先选number大的。 如：123，321，选择 321123，而不是123321
• 长度不同的number该如何决策？ 如：830，8301，选择 8308301 还是 8301830？

```String a1 = num1 + num2;
String s2 = num2 + num1;

```public String largestNumber(int[] nums) {
String[] s = new String[nums.length];
for (int i = 0; i < nums.length; ++i){
s[i] = nums[i] + "";
}
Arrays.sort(s, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String s1 = o1 + o2;
String s2 = o2 + o1;
return s1.compareTo(s2);
}
});

if (s[s.length - 1].charAt(0) == '0' ) return "0";
String ans = "";
for (String n : s){
ans = n + ans;
}
return ans;
}```

## Leetcode 440. K-th Smallest in Lexicographical Order

• 访问子结点， cur = cur * 10；
• 访问相邻结点，cur = cur + 1；

• 计算到相邻结点的步数，如果步数小于剩余k的能够行走的步数，访问子结点。
• 否则，访问邻居结点。

```private int calStep(int n, long n1, long n2){
int step = 0;
while (n1 <= n){
step += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return step;
}```

```    public int findKthNumber(int n, int k) {
int cur = 1;
k = k - 1;
while (k > 0){
int steps = calStep(n, cur, cur + 1);
if (steps <= k){
cur = cur + 1;
k -= steps;
}
else{
cur *= 10;
k -= 1;
}
}
return cur;
}

private int calStep(int n, long n1, long n2){
int step = 0;
while (n1 <= n){
step += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return step;
}```

0 条评论

• ### 挑战程序竞赛系列（81）：4.3 LCA（1）

挑战程序竞赛系列（81）：4.3 LCA（1） 传送门：POJ 2763: Housewife Wind 题意： XX村里有n个小屋，小屋之间有双向可达的道...

• ### 挑战程序竞赛系列（32）：4.5 A*与IDA*

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（36）：3.3线段树和平方分割

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### P1828 香甜的黄油 Sweet Butter

题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜...

• ### 51Nod-1203-JZPLCM

ACM模版 描述 ? 题解 这个题的解法好像好多好多，可以线段树解，自然也可以用树状数组解，还有大佬直接莫队推过，我这里用的树状数组搞得。 首先将数进行拆解，拆...

• ### 1751:分解因数

1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a，要求分解成若干个正整数的乘积，即a = ...

• ### 挑战程序竞赛系列（81）：4.3 LCA（1）

挑战程序竞赛系列（81）：4.3 LCA（1） 传送门：POJ 2763: Housewife Wind 题意： XX村里有n个小屋，小屋之间有双向可达的道...

• ### 口算训练 HDU - 6287

小Q非常喜欢数学，但是他的口算能力非常弱。因此他找到了小T，给了小T一个长度为n的正整数序列a1,a2,…,an，要求小T抛出m个问题以训练他的口算能力。

• ### 计算机二级大题.

1题 #include <iostream> using namespace std; class MyClass { public: MyClass(...