JS基础算法题（二）

时间：2020-08-17 22:32:33 收藏：0 阅读：97

1.1 数组去重的五种方法

数组去重：将数组中重复的元素去掉

JS数组没有删除具体元素的删除（只能删掉值，删不掉元素的索引），可以使用另外一个结构来进行存储
- 新数组
- 新对象
JS数组虽然本质可以删除第一个和最后一个元素，可以利用

这一特性，交换当前重复的元素到最后，然后进行删除（pop() 或者length--）

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        var arr = [20, 66, 88, 25, 66, 90, 88, 50];// [20,25,66,88,90,50]

        //1.排序法 : 最好理解

        // //1.1 对数组排序
        // arr.sort(function(a,b){
        //     return a-b;
        // });
        // console.log(arr);
        // //1.2 声明空数组存储去重后的数组
        // var newArr = [];
        // //1.3 遍历arr，检查arr[i]与arr[i+1]是否相等
        // for(var i = 0;i<arr.length;i++){
        //     if(arr[i] != arr[i+1]){
        //         newArr[newArr.length] = arr[i];
        //     };
        // };
        // console.log(newArr);




        //2.开关思想（假设成立法）

        // //2.1 声明空数组存储去重后的数组
        // var newArr = [];
        // //2.2 遍历arr，检查arr[i]在不在newArr中
        // for (var i = 0; i < arr.length; i++) {
        //     //开关思想 ： 某种操作结果只有两种清空。布尔类型存储两种情况。
        //     //1.声明开关
        //     var single = true;//假设不在
        //     //2.遍历newArr检查 只要与arr[i]相等
        //     for(var j = 0;j<newArr.length;j++){
        //         if(arr[i] == newArr[j]){
        //             single = false;
        //             break;//只要发现重复元素，后面没有必要比较
        //         };
        //     };
        //     //3. 根据开关结果实现需求
        //     if(single){
        //         newArr[newArr.length] = arr[i];
        //     };
        // };

        // console.log(newArr);
        


        //3.indexOf : 常用

        // //2.1 声明空数组存储去重后的数组
        // var newArr = [];
        // //2.2 遍历arr，检查arr[i]在不在newArr中
        // for (var i = 0; i < arr.length; i++) {
        //     if(newArr.indexOf(arr[i]) == -1){//不在
        //         newArr.push(arr[i]);
        //     }
        // };

        // console.log(newArr);

        //4.对象法

        var arr = [20, 66, 88, 25, 66, 90, 88, 50];

        /* 核心思路：利用对象的属性名不能重复
            对象的取值赋值特点
                取值 ： 存在，取值。 不存在，取undefined
                赋值 ： 存在，修改。 不存在，动态添加

        1.声明空对象 ： 检查数组元素是否重复 （元素作为属性名，检查对象有没有这个属性）
        2.声明空数组 ：存储去重后的数组
        3.遍历arr，检查arr[i]是否重复
         */
         var obj = {};
         var newArr = [];
         for(var i = 0;i<arr.length;i++){
            //检查对象有没有 arr[i] 这个属性？
            if(obj[arr[i]] == undefined){//未重复 
                newArr.push(arr[i]);
                obj[arr[i]] = 1;//这里赋值目的是为了下一次取值，不是undefined
            }
         };

         console.log(newArr);
        
        
        //5.重复元素自我交换删除法
        /*
        	核心思路：判定元素在数组中查到的位置是否是自身（元素是一定能找到的）
        		* 如果是自身：说明当前元素还没有重复
        		* 如果不是自身：说明当前元素在前面已经存在过：交换最后一个元素，然后把最后一个删除
        		
        	步骤：
        	1.遍历数组的每一个元素
        	2.判定当前遍历的元素在当前数组中存在的位置，判定位置是否是当当前自己的位置
        	2.1.是自己位置，说明前面没有重复，忽略
        	2.2.不是自己位置，说明前面已经存在：
        		2.2.1交换最后一个元素过来
        		2.2.2然后删除
        		2.2.3最后一个元素有可能已经与前面重复了，为了不跳过当前新交换的元素，重新从当前元素开始检索	
        */
        arr = [1,1,2,3,5,0,1];
        for (var i = 0; i < arr.length; i++) {
            //判定当前元素在数组中找出的位置
            if (arr.indexOf(arr[i]) != i) {
                //说明不是自己：前面已经存在过
                //交换最后一个元素过来（因为最后一个可以删除
                var temp = arr[i];
                arr[i] = arr[arr.length - 1];
                arr[arr.length - 1] = temp;
			  
                //删除最后一个元素：两种方式都可以
                // arr.pop();
                arr.length--;
                
                //最后一个元素有可能已经与前面重复了，所以为了保证安全，被交换过来的元素还要重新经受考验
                i--;
            }
        }
        
        //注意：以上方式会改变数组中原来元素的顺序位置

    </script>
</body>

</html>

1.2-循环嵌套练习：九九乘法表

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
    <script>
        /* 
        第一行 i= 1 ,列数 1
        第二行 i= 2 ,列数 2
        第三行 i= 3 ,列数 3
        ^^^
        i = 9 ,列数 9

        内层循环次数 = i
         */

        //1.外层循环 ： 行 9
        for(let i = 1;i<=9;i++){
            //2.内层循环次数 = i
            for(let j = 1;j<=i;j++){// i = 9 j = 1 2 3 4 5 6 7 8 9
                document.write(j + ‘*‘ + i + ‘=‘ + j*i + ‘&nbsp;&nbsp;‘);
            };
            document.write(‘<br><br>‘);
        };
        
    </script>
</body>
</html>

1.3-数组排序-冒泡算法

算法algorithm，是一种解决问题的方法

算法的目标：使用最少的内存，最短的时间，解决最多的问题

冒泡算法：

重复地走访过要排序的元素列，依次比较两个相邻的元素

顺序正确：代表位置正确，不需要交换

顺序错误：交换两个元素，让顺序正确

<script>
    /*
        冒泡算法（顺序：从小到大）
        1.从第一个元素开始，比较下一个元素
            * 如果前面一个大于后面的元素：交换
            * 如果前面一个小于或者等于后面的元素：不用动
        2.循环比较数组中的每一个元素：直到最大的那个元素到达数组最后
        
        3.一次循环，只能得出最大的数据排到最后，因此需要根据数组元素的长度来进行循环嵌套
            * 一次只能让当前最大的到最后（如果原来最大的就在最后，那么就是次大的）
            * 根据数组长度实现：每次都能得出一个最大，直到全部都排好序
    */
    
    // 定义一个无序数组
    let arr = [3,5,1,8,6,2];
    
    // 外部循环：决定里面循环的次数
    for(let i = 0;i < arr.length;i++){
        // 内部循环：决定当前最大的元素跑到正确的位置去
        for(let j = 0;j < arr.length - 1;j++){
            // j < arr.length - 1 是因为需要进行向后一个进行元素匹配
            
            // 判定当前元素与后一个元素的关系：前面大于后面：交换（其他情况不用变）
            if(arr[j] > arr[j+1]){
                // 交换两个元素的值：采用第三个变量
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    
    console.log(arr);        // [1,2,3,5,6,8]
</script>

原文：https://www.cnblogs.com/pongx/p/13515248.html

JS基础算法题（二）

1.1 数组去重的五种方法

1.2-循环嵌套练习：九九乘法表

1.3-数组排序-冒泡算法