已知A,B和C为3个递增有序的顺序表,编写算法,实现删除A表中既在B表中出现,又在C表中出现的所有元素。

时间复杂度O(n),空间复杂度O(1);

package sequenceList;

public class RemoveThePublicElement {
    public static void main(String[] args) {
        Integer[] A = {1, 2, 3, 4, 5, 6, 6, 7};
        Integer[] B = {2, 4, 6, 7, 9};
        Integer[] C = {1, 2, 2, 6, 8, 10};
        RemoveThePublicElement.removeThePublicElement(A, B, C);
        for (Integer e : A) {
            System.out.println(e);
        }
    }

    /**
     * @param listA 递增有序的顺序表 A
     * @param listB 递增有序的顺序表 B
     * @param listC 递增有序的顺序表 C
     * @param <T>   递增有序的顺序表的元素类型
     * @return 返回最终经过处理的递增有序的顺序表A
     */
    public static <T extends Comparable> void removeThePublicElement(T[] listA, T[] listB, T[] listC) {
        if (listA.length==0){
            throw new RuntimeException("顺序表A为空");
        }
        int indexB = 0, indexC = 0;       //indexA,indexB,indexC为扫描顺序表A,B和C的工作变量
        int currentAIndex = -1;           //currentAIndex用于记录A表中保留下来的元素在A表中的位置
        for (int indexA = 0; indexA < listA.length && indexB < listB.length && indexC < listC.length; indexA++) {
            while (listA[indexA].compareTo(listB[indexB]) > 0) {
                indexB++;
            }
            if (listA[indexA].compareTo(listB[indexB]) == 0) {
                while (listA[indexA].compareTo(listC[indexC]) > 0) {
                    indexC++;
                }
                if (listA[indexA].compareTo(listC[indexC]) == 0) {
                    continue;
                } else {
                    currentAIndex++;
                }
            } else {
                currentAIndex++;
            }
            listA[currentAIndex] = listA[indexA];
        }
        for (int i = currentAIndex + 1; i < listA.length; i++) {
            listA[i] = null;
        }
    }
}

 


版权声明:本文为qq_46539113原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。