《盘点那些秀你一脸的秒天秒地算法》（1）

一时失言乱红尘 2023-06-22 14:00 35阅读 0赞

本系列坚持格式：1个抖机灵算法+2个较简单但是天秀的算法+1个较难天秀算法。

# bogo排序 #

Bogo排序(Bogo-sort)，又被称为猴子排序，是一种恶搞排序算法。

**将元素随机打乱，然后检查其是否符合排列顺序，若否，则继续进行随机打乱，继续检查结果，直到符合排列顺序。**  
Bogo排序的最坏时间复杂度为O(∞)，一辈子也不能输出排序结果，平均时间复杂度为O(n·n!)。

这让我想到了另一个理论：猴子理论，只要让一只猴子一直敲打计算机，理论上会有一天，它能敲出一本圣经出来，但是这个概率小到宇宙毁灭也很难敲出来。。

真的不知道这个排序应该叫做天才还是垃圾哈哈哈，但是闲的没事的我就把他实现出来了。

public class Main {
    
    	public static void main(String[] args) {
    		int[] arr = { 9,8,7,6,5,4,3,2,1};
    		System.out.println("排序次数" + bogo(arr));
    		for (int i : arr) {
    			System.out.print(i + " ");
    		}
    	}
    	
    	public static int bogo(int[] arr) {
    		int count = 0;
    		while (!isOrdered(arr)) {
    			shuffle(arr);
    			count++;
    		}
    		return count;
    	}
    
    	// 判断是否有序方法
    	public static boolean isOrdered(int[] arr) {
    		for (int i = 1; i < arr.length; i++) {
    			if (arr[i - 1] > arr[i]) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	// 随机排序方法
    	public static void shuffle(int[] arr) {
    		int temp;
    		for (int i = 0; i < arr.length; i++) {
    			int j = (int) (Math.random() * arr.length);
    			temp = arr[i];
    			arr[i] = arr[j];
    			arr[j] = temp;
    		}
    	}
    
    }

**9是中国最大的数字嘛，我就把数组长度设为9，结果平均排序次数要60万次，不知道我的运气怎么样哈哈，你们也试试吧？**

然而，有个看似笑话的方法声称可以用O(n)实现Bogo排序，依照量子理论的平行宇宙解释，使用量子随机性随机地重新排列元素，不同的可能性将在不同的宇宙中展开，总有一种可能猴子得到了正确的顺序，量子计算机找到了这个宇宙后，就开始毁灭其他排序不成功的宇宙，剩下一个观察者可以看到的正确顺序的宇宙。

如果想要迈出这个看似荒诞，但令人无比兴奋的"高效算法"的第一步，请先证明"平行宇宙解释"的正确性。

# 位运算 #

关于位运算有很多天秀的技巧，这里举一个例子。

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: \[2,2,1\]输出: 1  
示例 2:

输入: \[4,1,2,1,2\]输出: 4

思路：拿map，set，都不符合要求，那怎么办呢？

我们知道什么数字和自己异或，都等于0.

什么数字和0异或，都等于它本身，

异或又符合交换律

所以全部异或一遍，答案就是那个出现一次的数字。

class Solution {
        public int singleNumber(int[] nums) {
            int ans = 0;
            for(int i :nums)ans ^= i;
            return ans;
        }
    }

有没有被秒了？

# 打擂台 #

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

把狂野般的思绪收一收，咱们来看看最优解。

class Solution {
        public int majorityElement(int[] nums) {
            int count = 0;//当前答案出现的次数
            Integer candidate = null;//答案
    
            for (int num : nums) {
                if (count == 0) candidate = num;
                count += (num == candidate) ? 1 : -1;
            }
    
            return candidate;
        }
    }

我来解释一下策略：记录当前的答案candidate ，记录count。这时，我们遍历了一个新的数字，如果和candidate 一样，我们就让count+1，否则让count-1.如果count变成了0，那candidate 就下擂台，换新的擂主（数字）上，也就是说把candidate 更新成新的数字，count也更新成1.

最后在擂台上的一定是答案。

**肯定有人怀疑这个做法的正确性吧？我就来说一下它为啥对？**

首先，我们想像一下对最终隐藏答案ans最不利的情况：每个其他数字全部都打擂这个答案ans，那ans的count最后也会剩1，不会被打下来。

正常情况呢？其他数字还会互相打擂，这些数字如此“内耗”，又怎么能斗得过最终答案ans呢？对不对？

#  #

# morris遍历 #

通常，实现二叉树的前序（preorder）、中序（inorder）、后序（postorder）遍历有两个常用的方法：一是递归(recursive)，二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度（递归本身占用stack空间或者用户自定义的stack），我分别给出一个例子

递归：

void PreorderTraversal( BinTree BT )
    {
        if(BT==NULL)return ;
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }

非递归：

*p=root;
    while(p || !st.empty())
    {
        if(p)//非空
        {
            //visit(p);进行操作
            st.push(p);//入栈
            p = p->lchild;左
        } 
        else//空
        {
            p = st.top();//取出
            st.pop();
            p = p->rchild;//右
        }
    }

为啥这个O(n)的空间就是省不掉呢？因为我们需要空间来记录之前的位置，好在遍历完了可以回到父节点。所以这个空间是必须的！如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

比如我们遍历2，想遍历4，这时候我们要保证遍历完4以后，还能回到2，我们好去继续遍历5等等结点，所以必须花空间记录。

**但是，还就有这么一种算法，能实现空间O(1)的遍历，服不服。**

你们可能会问，你刚说的，必须有空间来记录路径，怎么又可以不用空间了呢？

这就是morris遍历，它其实是**利用了叶子节点大量的空余空间**来实现的，只要把他们利用起来，我们就可以省掉额外空间啦。

我们不说先序中序后序，先说morris遍历的原则：

**1、如果没有左孩子，继续遍历右子树，比如：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1][]

这个2就没有左孩子，这时直接遍历右孩子即可。

**2、如果有左孩子，找到左子树最右节点。**

比如上图，6就是2的最右节点。

1）如果最右节点的右指针为空（说明第一次遇到），把它指向当前节点，当前节点向左继续处理。

修改后：

![20191216204441238.png][]

2）如果最右节点的右指针不为空（说明它指向之前结点），把右指针设为空，当前节点向右继续处理。

这就是morris遍历。

**请手动模拟深度至少为4的树的morris遍历来熟悉流程。**

**下面给出实现：**

定义结点：

public static class Node {
    		public int value;
    		Node left;
    		Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

先序：（完全按规则写就好。）

//打印时机（第一次遇到）：发现左子树最右的孩子右指针指向空，或无左子树。
    	public static void morrisPre(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					System.out.print(cur1.value + " ");
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}
    			} else {
    				System.out.print(cur1.value + " ");
    			}
    			cur1 = cur1.right;
    		}
    		System.out.println();
    	}

morris在发表文章时只写出了中序遍历。而先序遍历只是打印时机不同而已，所以后人改进出了先序遍历。至于后序，是通过打印所有的右边界来实现的：对每个有边界逆序，打印，再逆序回去。注意要原地逆序，否则我们morris遍历的意义也就没有了。

完整代码：

public class MorrisTraversal {
    	public static void process(Node head) {
    		if(head == null) {
    			return;
    		}
    		// 1
    		//System.out.println(head.value);
    		process(head.left);
    		
    		// 2
    		//System.out.println(head.value);
    		process(head.right);
    		
    		// 3
    		//System.out.println(head.value);
    	}
    	
    	
    	public static class Node {
    		public int value;
    		Node left;
    		Node right;
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    
    //打印时机：向右走之前
    	public static void morrisIn(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;//当前节点
    		Node cur2 = null;//最右
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			//左孩子不为空
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}//找到最右
    				//右指针为空，指向cur1，cur1向左继续
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}//右指针不为空，设为空
    			}
    			System.out.print(cur1.value + " ");
    			cur1 = cur1.right;
    		}
    		System.out.println();
    	}
    
    //打印时机（第一次遇到）：发现左子树最右的孩子右指针指向空，或无左子树。
    	public static void morrisPre(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					System.out.print(cur1.value + " ");
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}
    			} else {
    				System.out.print(cur1.value + " ");
    			}
    			cur1 = cur1.right;
    		}
    		System.out.println();
    	}
    
    //逆序打印所有右边界
    	public static void morrisPos(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    					printEdge(cur1.left);
    				}
    			}
    			cur1 = cur1.right;
    		}
    		printEdge(head);
    		System.out.println();
    	}
    //逆序打印
    	public static void printEdge(Node head) {
    		Node tail = reverseEdge(head);
    		Node cur = tail;
    		while (cur != null) {
    			System.out.print(cur.value + " ");
    			cur = cur.right;
    		}
    		reverseEdge(tail);
    	}
    //逆序（类似链表逆序）
    	public static Node reverseEdge(Node from) {
    		Node pre = null;
    		Node next = null;
    		while (from != null) {
    			next = from.right;
    			from.right = pre;
    			pre = from;
    			from = next;
    		}
    		return pre;
    	}
    	public static void main(String[] args) {
    		Node head = new Node(4);
    		head.left = new Node(2);
    		head.right = new Node(6);
    		head.left.left = new Node(1);
    		head.left.right = new Node(3);
    		head.right.left = new Node(5);
    		head.right.right = new Node(7);
    
    		morrisIn(head);
    		morrisPre(head);
    		morrisPos(head);
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191216203828458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191216204334673.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191216204441238.png]: https://img-blog.csdnimg.cn/20191216204441238.png