【数据结构与算法之排序与查找】案例

清疚 2024-03-25 16:39 86阅读 0赞

#### 【数据结构与算法之排序与查找】案例 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】案例
         *   *   *  1 荷兰国旗问题
                 *  2 重复数字出现的次数

###### 1 荷兰国旗问题 ######

荷兰国旗由红、白、蓝三色构成，

![在这里插入图片描述][ee8f379f03fe4687bf94a5bce0bbb6c1.png_pic_center]

有一个由红、白、蓝三种颜色的n 个条块组成的序列，请设计一个时间复杂度为 O ( n ) O(n) O(n) 的算法，将这些条块按照红、白、蓝的顺序排好，也就是构成荷兰国旗的图案。

【思路分析】将这个问题抽象化，用一个数组来存放这三种颜色的色块，其中0 表示红色条块，1 表示白色条块，2 表示蓝色条块。开始时，三种颜色的色块在数组中是无序的，要求将数组中的元素按照0 → 1 → 2 的顺序排列

![在这里插入图片描述][a2b1945c2cc84ee9a13e2fbcd46e2a4d.png_pic_center]

Java 算法实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: DutchFlagIssue
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 14:11
     */
    
    public class DutchFlagIssue {
        
    
        public static void arrangeHollandFlag(int[] array) {
        
            int i, j;
    
            for (i = 0; array[i] == 0; i++) ; // i 最终指向第1个非0的元素
            for (j = array.length - 1; array[j] == 2; j--) ; // j 最终指向第1个非2的元素
    
            int cur = i; // cur在[i, j] 之间扫描数据元素
    
            while (cur <= j) {
        
                if (array[cur] == 0) {
        
                    int tmp = array[i];
                    array[i] = array[cur]; // 交换元素
                    array[cur] = tmp;
    
                    i++;
                    cur++;
                    continue;
                }
                if (array[cur] == 2) {
        
                    int tmp = array[j];
                    array[j] = array[cur]; // 交换元素
                    array[cur] = tmp;
    
                    while (array[j] == 2) {
        
                        j--; // j 始终指向最后一个非2的元素
                    }
                    continue;
                }
                cur++;
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 2, 1, 0, 2, 1, 0, 1, 2, 2, 0, 0, 0, 1, 2};
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
            arrangeHollandFlag(array);
            System.out.println("\n排序后:");
            for (int i : array) {
        
                System.out.print(i + " ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][25f6ba637724481ca0e54e752b8a66bd.png_pic_center]

###### 2 重复数字出现的次数 ######

已知有一个从小到大的有序整型数组，编写程序，找出某个数字出现的次数。

【折半找的改进】

Java 算法实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: GetRepeatNumberCount
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 14:23
     */
    
    public class GetRepeatNumberCount {
        
    
        public static int getBoundaryIndex(int[] array, int key, boolean forStart) {
        
            int low = 0, high = array.length;
            int mid = 0;
            int last = -1;  // 用last记录start或者end
    
            while (low <= high) {
        
                mid = (low + high) / 2;
                if (array[mid] < key) {
        
                    low = mid + 1;
                } else if (array[mid] > key) {
        
                    high = mid - 1;
                } else {
         // 找到了key
                    last = mid;
                    if (forStart) {
        
                        high = mid - 1;
                    } else {
        
                        low = mid + 1;
                    }
                }
            }
    
            return last;
        }
    
        public static int getRepeatNumberCount(int[] array, int key) {
        
            int start, end;
            start = getBoundaryIndex(array, key, true);
            end = getBoundaryIndex(array, key, false);
    
            if (start == -1 || end == -1) {
        
                return 0;
            } else {
        
                return end - start + 1;
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        0, 1, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 9, 12};
            int numberCount = getRepeatNumberCount(array, 5);
    
            System.out.println(numberCount);
    
        }
    
    }

运行结果

![在这里插入图片描述][60667496a3e445849eb546324244539f.png_pic_center]

[ee8f379f03fe4687bf94a5bce0bbb6c1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ed863cd76e86467999a3e07a7874ee7c.png
[a2b1945c2cc84ee9a13e2fbcd46e2a4d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ef34d298ecc943a09dc4f8fece5b0421.png
[25f6ba637724481ca0e54e752b8a66bd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3f0c544e546c4e66ab43ddfad16a6fa7.png
[60667496a3e445849eb546324244539f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3a562194893d489aa7b06b424aefd50c.png