颜色分类--荷兰国旗问题

附上一道shell编程题，关于统计词频，只需一行命令即可解决，码住可能对以后处理文本有用。
写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

为了简单起见，你可以假设：

words.txt只包括小写字母和 ' ' 。
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。
示例:

假设 words.txt 内容如下：

the day is sunny the the
the sunny is is
你的脚本应当输出（以词频降序排列）：

the 4
is 3
sunny 2
day 1
说明:

不要担心词频相同的单词的排序问题，每个单词出现的频率都是唯一的。
你可以使用一行 Unix pipes 实现吗？

链接：https://leetcode-cn.com/problems/word-frequency

• 题解：参考大佬

cat words.txt | xargs -n 1 | sort | uniq -c | sort -nr | awk '{print $2" "$1}'

• xargs 分割字符串 -n 1表示每行输出一个 可以加-d指定分割符
• 要使用uniq统计词频需要被统计文本相同字符前后在一起，所以先排序 uniq -c 表示同时输出出现次数
• sort -nr 其中-n表示把数字当做真正的数字处理(当数字被当做字符串处理，会出现11比2小的情况)
  -题解2：参考评论区

cat words.txt | tr -s ' ' '\n'|sort|uniq -c |sort -r|awk '{print $2" "$1}'

cat ——浏览文件
tr -s ——替换字符串（空格换为换行）保证了一行一个单词
sort ——默认ASCII值排序，排序号后还会有重复
uniq —— 去重，-c再输出重复次数。结果就是 ”4 abc“ abc出现了4次
sort -r —— 反向排序，也就是从大到小。得到按频率高低的结果
awk ——格式化输出，规定输出是先字符串再重复次数，所以先$2再$1，中间空格分隔

• 补充：
  • xargs 命令

格式：somecommand |xargs -item  command

  1. xargs 是给命令传递参数的一个过滤器，也是组合多个命令的一个工具。
  2. xargs 可以将管道或标准输入（stdin）数据转换成命令行参数，也能够从文件的输出中读取数据。
  3. xargs 也可以将单行或多行文本输入转换为其他格式，例如多行变单行，单行变多行。
  4. xargs 默认的命令是 echo，这意味着通过管道传递给 xargs 的输入将会包含换行和空白，不过通过 xargs 的处理，换行和空白将被空格取代。
  5. xargs 是一个强有力的命令，它能够捕获一个命令的输出，然后传递给另外一个命令。

---

• 题目描述：
  给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
链接：https://leetcode-cn.com/problems/sort-colors

• 解题思路：设置P0，Pcur，P2三个指针，先确定0，2的边界，再移动cur指针进行两两比较，若等于0或2，则交换，并移动指针。官方演示思路最清楚
  

  示意图
  • 说明：
    初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
    初始化2的最左边界 ：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
    初始化当前考虑的元素序号 ：curr = 0.

While curr <= p2 :
若 nums[curr] = 0 ：交换第 curr个和第p0个元素，并将指针都向右移。
若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将p2指针左移 。
若 nums[curr] = 1 ：将指针curr右移。

• Python版：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        '''
        荷兰三色旗问题解
        '''
        # 对于所有 idx < p0 : nums[idx < p0] = 0 
        # curr是当前考虑元素的下标
        p0 = curr = 0
        # 对于所有 idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1

        while curr <= p2:  # important condition
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]  # swap position
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

• Tips: 关于只有左边界移动后加1，而右边界不需要的问题

  • 关于左边界，可以分为两种情况：扫描到0或1
  • 当扫描到0时，P0的右边界 > Pcur，所以需要cur += 1；若不自增，则下一轮循环，可能出现重复比较
  • 当扫描到1时，无需比较，直接自增
  • 关于右边界，只有一种情况：扫描到2
  • 所以只起到交换作用，并没有扫描，无需自增

• C++版

class Solution {
  public:
  /*
  荷兰三色旗问题解
  */
  void sortColors(vector<int>& nums) {
    // 对于所有 idx < p0 : nums[idx < p0] = 0
    // curr 是当前考虑元素的下标
    int p0 = 0, curr = 0;
    // 对于所有 idx > p2 : nums[idx > p2] = 2
    int p2 = nums.size() - 1;

    while (curr <= p2) {
      if (nums[curr] == 0) {
        swap(nums[curr++], nums[p0++]);
      }
      else if (nums[curr] == 2) {
        swap(nums[curr], nums[p2--]);
      }
      else curr++;
    }
  }
};

• Tips:

  • 注意c++和python交换值的方式

• Java版

class Solution {
  /*
  荷兰三色旗问题解
  */
  public void sortColors(int[] nums) {
    // 对于所有 idx < i : nums[idx < i] = 0
    // j是当前考虑元素的下标
    int p0 = 0, curr = 0;
    // 对于所有 idx > k : nums[idx > k] = 2
    int p2 = nums.length - 1;

    int tmp;
    while (curr <= p2) {
      if (nums[curr] == 0) {
        // 交换第 p0个和第curr个元素
        // i++，j++
        tmp = nums[p0];
        nums[p0++] = nums[curr];
        nums[curr++] = tmp;
      }
      else if (nums[curr] == 2) {
        // 交换第k个和第curr个元素
        // p2--
        tmp = nums[curr];
        nums[curr] = nums[p2];
        nums[p2--] = tmp;
      }
      else curr++;
    }
  }
}

• Tips：
  • 利用tmp交换