精华内容
下载资源
问答
  • 无序数组变成有序数组并且去重
    2021-07-24 19:36:13

    无序数组变成有序数组并且去重

    面试2:用代码实现无序数组变成有序数组并且去重
    例如:{5, 6, 8, 9, 6, 5, 4, 9, 8, 7}
    结果:[4, 5, 6, 7, 8, 9]

    import java.util.*;
    public class Interview{
        public static void main(String[] args) {
    		int[] strs = {5, 6, 8, 9, 6, 5, 4, 9, 8, 7};
            //对数组进行排序
            Arrays.sort(strs);
            HashSet hashSet = new HashSet();
            //HashSet不允许储存重复元素
            for (int str : strs) {
                hashSet.add(str);
            }
            Object[] objects = hashSet.toArray();
            System.out.println(Arrays.toString(objects));
        }
    }
    
    更多相关内容
  • 1、求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低 2、例如: lists = [3, 2, 1, 4] , 中位数为 = ...
  • 主要介绍了C++算法之在无序数组中选择第k小个数的实现方法,涉及C++数组的遍历、判断、运算等相关操作技巧,需要的朋友可以参考下
  • 今天小编就为大家分享一篇关于Java查找不重复无序数组中是否存在两个数字的和为某个值,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 无序数组去重算法

    2022-02-18 14:44:15
    无序数组去重算法 无序数组去重算法的复杂度是O(n2)。 代码如下,首先进行外层循环,复杂度O(n),然后查找这个元素之前的元素中有没有重复的,复杂度O(n),如果有就删除,复杂度O(1),没有就下一个元素,复杂度O(1)。...

    无序数组去重算法

    无序数组去重算法的复杂度是O(n2)。

    代码如下,首先进行外层循环,复杂度O(n),然后查找这个元素之前的元素中有没有重复的,复杂度O(n),如果有就删除,复杂度O(1),没有就下一个元素,复杂度O(1)。加起来复杂度O(n2)。

    完整代码在github上面,只需要clone下来执行composer install然后执行 php artisan test:unsortDeduplicate 就可以看到结果了

        /**
         * Execute the console command.
         *
         * @return mixed
         */
        public function handle()
        {
            $a = [4,5,4,3,8,6,6,10,34,10,4];
            dump($a);
            $i = 1;
            $len = count($a);
            dump("长度:".$len);
            while ($i < $len) { //循环全部数据
                //在整个数组中寻找这个值,如果找到了就删除他,如果没找到就下一个
                $preIndex = $this->find($i, $a);
                if ($preIndex!==false) {unset($a[$preIndex]);}
                else $i++;
            }
            dd($a);
        }
    
        private function find($i, array $a) {
            $index = 0;
            //循环从0到这个下标
            while ($index < $i) {
                //不存在说明被删除了
                if (!array_key_exists($index, $a)) {$index++;continue;}
                //如果找到了返回下标
                if ($a[$i] == $a[$index]) return $index;
                else $index++;
            }
            return false;
        }
    
    展开全文
  • 原文地址: 无序数组求第K大的数 问题描述 无序数组求第K大的数,其中K从1开始算。 例如:[0,3,1,8,5,2]这个数组,第2大的数是5 OJ可参考:LeetCode_0215_KthLargestElementInAnArray 堆解法 设置一个小根堆,先把前K...

    作者:Grey

    原文地址: 求无序数组求第K大的数

    问题描述

    无序数组求第K大的数,其中K从1开始算。

    例如:[0,3,1,8,5,2]这个数组,第2大的数是5

    OJ可参考:LeetCode 215. Kth Largest Element in an Array

    堆解法

    设置一个小根堆,先把前K个数放入小根堆,对于这前K个数来说,堆顶元素一定是第K大的数,接下来的元素继续入堆,但是每入一个就弹出一个,最后,堆顶元素就是整个数组的第K大元素。代码如下:

    class Solution {
        public static int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for (int i = 0; i < k; i++) {
                heap.offer(nums[i]);
            }
            for (int i = k; i < nums.length;i++) {
                heap.offer(nums[i]);
                heap.poll();
            }
            return heap.peek();
        }
    }
    

    由于每次堆需要承担logK的调整代价, 所以这个解法的时间复杂度为O(N*logK)

    改进快排算法

    快速排序中,有一个partition的过程, 这个过程随机选择数组中的一个数,假设叫pivot,这个过程主要作用是将数组的l...r区间内的数:

    • 小于pivot的数放右边

    • 大于pivot的数放左边

    • 等于pivot的数放中间

    返回两个值,一个是左边界和一个右边界,位于左边界和右边界的值均等于pivot,小于左边界的位置的值都大于pivot,大于右边界的位置的值均小于pivot。简言之:如果要排序,pivot这个值在一次partition以后,所在的位置就是最终排序后pivot应该在的位置。

    所以,如果数组中某个数在经历上述partion之后正好位于K-1位置,那么这个数就是整个数组第K大的数。

    快排改进算法完整代码如下:

    class Solution {
           public static int findKthLargest(int[] nums, int k) {
            return process(nums, 0, nums.length - 1, k - 1);
        }
    
        // arr 在L...R范围内,如果要从大到小排序,请返回index位置的值
        private static int process(int[] arr, int L, int R, int index) {
            if (L == R) {
                return arr[R];
            }
            int pivot = arr[L + (int) (Math.random() * (R - L + 1))];
            int[] range = partition(arr, L, R, pivot);
            if (index >= range[0] && index <= range[1]) {
                return pivot;
            } else if (index < range[0]) {
                return process(arr, L, range[0], index);
            } else {
                return process(arr, range[1], R, index);
            }
        }
    
        public static int[] partition(int[] arr, int L, int R, int pivot) {
            int less = L - 1;
            int more = R + 1;
            while (L < more) {
                if (arr[L] > pivot) {
                    swap(arr, L++, ++less);
                } else if (arr[L] == pivot) {
                    L++;
                } else {
                    swap(arr, L, --more);
                }
            }
            return new int[]{less + 1, more - 1};
        }
        
        public static void swap(int[] nums, int t, int m) {
            int tmp = nums[m];
            nums[m] = nums[t];
            nums[t] = tmp;
        }
    }
    

    其中process方法表示:numsL...R范围上,如果要排序(从大到小)的话,请返回index位置的值。

    int pivot = nums[L + (int) (Math.random() * (R - L + 1))];
    

    这一行表示随机取一个值pivot出来,用这个值做后续的partition操作,如果index恰好在pivot这个值做partition的左右边界范围内,则pivot就是排序后第index+1大的数(从1开始算)。

    bfprt算法

    brfpt算法和改进快排算法主流程上基本一致,只是在选择pivot的时候有差别,快排改进是随机取一个数作为pivot, 而bfprt算法是根据一定的规则取pivot,核心代码为:

    public class LeetCode_0215_KthLargestElementInAnArray {
        ......
        // nums在L...R范围上,如果要排序(从大到小)的话,请返回index位置的值
        public static int bfprt(int[] nums, int L, int R, int index) {
            if (L == R) {
                return nums[L];
            }
            //int pivot = nums[L + (int) (Math.random() * (R - L + 1))];
            int pivot = medianOfMedians(nums, L, R);
            int[] range = partition(nums, L, R, pivot);
            if (index >= range[0] && index <= range[1]) {
                return pivot;
            } else if (index < range[0]) {
                return bfprt(nums, L, range[0] - 1, index);
            } else {
                return bfprt(nums, range[1] + 1, R, index);
            }
        }
        ......
    }
    

    其中

    int pivot = medianOfMedians(nums, L, R);
    

    就是bfprt算法最关键的步骤,mediaOfMedians这个函数表示:

    num分成每五个元素一组,不足一组的补齐一组,并对每组进行排序(由于固定是5个数一组进行排序,所以排序的时间复杂度O(1)),取出每组的中位数,组成一个新的数组, 对新的数组求其中位数,这个中位数就是我们需要的值pivot

        public static int medianOfMedians(int[] arr, int L, int R) {
            int size = R - L + 1;
            int offSize = size % 5 == 0 ? 0 : 1;
            int[] mArr = new int[size / 5 + offSize];
            for (int i = 0; i < mArr.length; i++) {
                // 每一组的第一个位置
                int teamFirst = L + i * 5;
                int median = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4));
                mArr[i] = median;
            }
            return bfprt(mArr, 0, mArr.length - 1, (mArr.length - 1) / 2);
        }
    
        public static int getMedian(int[] arr, int L, int R) {
            Arrays.sort(arr, L, R);
            return arr[(R + L) / 2];
        }
    

    注:mediaOfMedians方法中最后一句:

    return bfprt(mArr, 0, mArr.length - 1, (mArr.length - 1) / 2);
    

    就是利用bfprt算法拿整个元素中间位置的值。

    关于bfprt算法的两个问题

    1. 为什么是5个一组

    2. 为什么严格收敛到O(N)

    请参考:

    BFPRT算法原理

    BFPTR算法详解+实现+复杂度证明

    三种解法复杂度分析

    算法时间空间
    O(N*logK)O(N)
    快排改进概率上收敛到:O(N)O(1)
    bfprt严格收敛到:O(N)O(N)

    相关题目

    寻找两个正序数组的中位数

    OJ见:LeetCode 4. Median of Two Sorted Arrays

    代码见:LeetCode_0004_MedianOfTwoSortedArrays

    第K小的数值对

    长度为N的数组arr,一定可以组成N^2个数值对。例如arr = [3,1,2],数值对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2),也就是任意两个数都有数值对,而且自己和自己也算数值对。数值对怎么排序?规定,第一维数据从小到大,第一维数据一样的,第二维数组也从小到大。所以上面的数值对排序的结果为:(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3), 给定一个数组arr,和整数k,返回第k小的数值对。

    代码见:Code_0015_KMinPair

    更多

    算法和数据结构笔记

    参考资料

    程序员代码面试指南(第2版)

    算法和数据结构体系班-左程云

    BFPRT算法原理

    BFPTR算法详解+实现+复杂度证明

    展开全文
  • 无序数组找中位数

    千次阅读 2021-04-04 09:27:11
    1.无序数组找中位数 思路一 把无序数组排好序,取出中间的元素 时间复杂度 采用普通的比较排序法 O(N*logN) 如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N). 思路二 (1)将前(n+1)/2个...

    1.无序数组找中位数

    1. 思路一
      把无序数组排好序,取出中间的元素
      时间复杂度 采用普通的比较排序法 O(N*logN)
      如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N).

    2. 思路二
      (1)将前(n+1)/2个元素调整为一个小顶堆
      (2)对后续的每一个元素,和堆顶比较,如果小于等于堆顶,丢弃之,取下一个元素。 如果大于堆顶,用该元素取代堆顶,调整堆,取下一元素。重复2.2步
      (3)当遍历完所有元素之后,堆顶即是中位数。
      注:如果数组元素的个数是奇数,取数组前(size+1)/2个元素建堆,如果是偶数则取前 size/2 个元素建堆。但如果是数据流,数据个数是动态变动的,则应采用小根堆+大根堆的办法,具体见本文第5点介绍。

    3. 思路三
      找中位数也可以用快排分治的思想。具体如下:
      (1)任意挑一个元素,以改元素为支点,划分集合为两部分,如果左侧集合长度恰为 (n-1)/2,那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧,反之,中位数在左侧。
      (2)进入相应的一侧继续寻找中位点。
      注:可参考快排思想实现Top K

    拓展:查找N个元素中的第K个小的元素,假设内存受限,仅能容下K/4个元素
    分趟查找:

    1. 第一趟,用堆方法查找最小的K/4个小的元素,同时记录剩下的N-K/4个元素到外部文件。
    2. 第二趟,用堆方法从第一趟筛选出的N-K/4个元素中查找K/4个小的元素,同时记录剩下的N-K/2个元素到外部文件。
    3. 第四趟,用堆方法从第一趟筛选出的N-K/3个元素中查找K/4个小的元素,这是的第K/4小的元素即使所求。

    https://blog.csdn.net/zdl1016/article/details/4676882


    2.将十进制数字转化为X 进制的字符串

    //将十进制数转化为X进制字符串 
    string trans(int num, int base){
    	string str;
    	while(num > 0){
    		if(num % base < 10)
    			str += num % base + '0';
    		else
    			str += num % base - 10 + 'A';
    		num = num / base;
    	}
    	reverse(str.begin(),str.end());
    	
    	return str;
    }
    

    3.找出字符串中第k次出现的字符

    1. 思路一
      遍历这个字符串(缺点是要对这个字符串查找好多次)
    2. 思路二
      (1) 先创建一个数组然后这个数组你就放成256个元素。
      (2) 把这个字符串转化成ASCLL码进行查找。(因为ASCLL码的范围比较小)
      (3) 当我们发现字符串中出现a(a的ASCLL为97)的时候,我们可以把刚才256个元素中下边为97的元素的值加一。
    char find_first_K(string str, int K)
    {
    	int count[256] = { 0 };
    	for (char ch : str) ++count[ch];
    
    	for (char ch : str) {
    		if (count[ch] == K)
    			return ch;
    	}
    
    	return '0';
    }
    

    5.找出数据流中的中位数

    在这里插入图片描述

    注意:始终保证小根堆A中元素个数不少于大根堆B中的元素个数,即A、B元素相等时,将B中最大元素加入A,否则将A中最小元素加入B,来维持元素个数平衡。

    class MedianFinder {
    private:
        priority_queue<int,vector<int>, greater<int>> A;    //小根堆
        priority_queue<int,vector<int>, less<int>> B;       //大根堆
    
    public:
        //插入新元素
        void addNum(int num) {
            if(A.size()==B.size()){ //把B中最大元素加入到A
                B.push(num);
                A.push(B.top());
                B.pop();
            }else{                  //把A中最小元素加入到B
                A.push(num);
                B.push(A.top());
                A.pop();
            }
        }
        
        //查找当前中位数
        int findMedian() {
            return A.size()==B.size()?(A.top()+B.top())/2.0:A.top();
        }
    };
    

    6.英文字符串流和中文字符串流如何分词

    一种对英文字符串进行分词的方法:https://d.wanfangdata.com.cn/periodical/jsjyyyj200707016

    字典与统计相结合的中文分词方法:https://d.wanfangdata.com.cn/periodical/xxwxjsjxt200609039

    暴力方法:

    1. 英文分词:根据字符串中的空格、标点符号进行分词。
    2. 中文分词:固定两个字为一词进行拆分。

    7.10亿QQ号去重

    1. 内存够的情况

    分段、map、多线程。

    1. 分段:哈希分桶,根据哈希值对桶数目取模得到对应桶号。
    2. map:需要计数采用unordered_map去重;不需要计数采用set去重。
    3. 多线程:将数据进行哈希分桶之后,各桶内map的去重可以采用多线程执行。

    2. 内存不够的情况

    思路一:bitmap

    位图bitmap:每个int数字只用一个比特位来做标记

    位图的操作(算法)基本依赖于下面3个元操作:

    set_bit(char x, int n); //将x的第n位置1,可以通过x |= (1 << n)来实现
    
    clr_bit(char x, int n); //将x的第n位清0,可以通过x &= ~(1 << n)来实现
    
    get_bit(char x, int n); //取出x的第n位的值,可以通过(x >> n) & 1来实现
    

    比如,要对数字int x = 1848105做标记,就可以调用set_bit(bit_map[x/8], x%8);

    除法看做求“组编号”,x/8即是 以8个位为一个小组,分组到编号为idx = x/8的bit_map元素中,然后在组内偏移lft = x%8个比特位。

    10亿数字(int 32位):10^8 * 32 / 8 = 40亿字节 / 1024 ≈ 400万 KB / 1024 ≈ 4000 MB / 1024 ≈ 4 GB
    int 32位所需bitmap大小:2^32 / 8 = 2^29 字节 / 1024 = 2^19 KB / 1024 = 2^9 MB = 512 MB

    10亿数字(long long 64位):4 GB * 2 = 8GB
    long long 64位所需bitmap大小:2^64 / 2^23 = 2^41 MB / 1024 = 2^31 GB / 1024 = 2^21 TB / 1024 = 2048 PB = 2 EB

    https://www.cnblogs.com/zhanghaiba/p/3594559.html

    思路二:多路归并排序

    问题:如何给100亿个数字排序?

    注:100亿个 int 型数字放在文件里面大概有 37.2GB

    1. 把这个37GB的大文件,用哈希分成1000个小文件,每个小文件平均38MB左右(理想情况),把100亿个数字对1000取模,模出来的结果在0到999之间,每个结果对应一个文件,所以我这里取的哈希函数是 h = x % 1000,哈希函数取得”好”,能使冲突减小,结果分布均匀。
    2. 按各输入文件中下一个读到的元素的大小构造一个输入流最小堆.
    3. 从堆顶文件里读一个元素并写入输出文件.
    4. 同时按读的那个文件的下一个元素的值调整堆.
    5. 若第3步已到达文件结尾.则从堆中删除该输入流.
    6. 如果堆中还有元素. 回到第2步.

    3. 外存不够的情况

    考虑是不是可以进行分布式处理

    待查~


    展开全文
  • classArray{//定义一个有序数组private long[] a;//定义数组长度private intnElems;//构造函数初始化public Array(intmax){a= new long[max];nElems= 0;}//size函数public intsize(){returnnElems;}//定义添加函数...
  • 二分法能在无序数组中查找,也能实现用二分法在无序数组中找第k小的数。时间复杂度是O(NlongN)。 对上边代码做一点小的改动即可实现。 public class disorderSearchBin { public static int ...
  • 【算法面试题】两数之和-无序数组
  • 基本思路:对数组进行排序,直接访问数组中位数 double MIDnum(vector<int>& array) { if(array.empty()) return -1; int midIndex = (array.size() - 1) / 2; sort(array.begin(), array.end()); if...
  • 文章目录前言一篇文章、40分钟演示如何将无序数组放到二叉树中01 设计思路:02 冒泡排序:03 二叉树基本概念:04 实战: 前言   如果您觉得有用的话,记得给博主点个赞,评论,收藏一键三连啊,写作不易啊^ _ ^。   ...
  • 合并两个有序数组: 给你两个按 非递减顺序 排列的整数数组nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列...
  • 由于只要求找出第k大的数,没必要将数组中所有值都排序。 典型解法:快速排序分组。 在数组中找到第k大的元素 取基准元素,将元素分为两个集合,一个集合元素比基准小,另一个比基准大 ,三种情况。 1.比基准大的...
  • 无序数组的查询

    2021-06-29 14:35:58
    #include <stdlib.h> #include <stdio.h> int main() { int nums[10] = {0, 10, 6, 296, 177, 23, 0, 100, 34, 999};//数组 ...//a代表数组下标b代表目标的下标c代表输入的数 ...a++) //在十个数组里循环查.
  • 无序数组的去重

    2020-11-10 10:39:43
    //对于字符数组去重也实用 //char str[] = {"Hello Hello"}; //对于字符串去重也实用(内存有一个'\0')可以用strlen int a[] = {5,5,1,3,3,2,3,4,2,2,5}; int i, j; int n = sizeof(a)/sizeof(int); //计算有多少...
  • 无序数组和有序数组

    千次阅读 2019-05-11 10:34:56
    有序数组的最大的好处在于查找的时间复杂度是O(log n),而无序数组的时间复杂度是O(n)。 有序数组的缺点是插入的世家复杂度是O(n),因为值大的元素需要往后移来给新元素腾位置,相反,无序数组的插入时间...
  • // 打乱有序的数组 let arr = [1,2,3,4,5] let newArr = [] var len = arr.length function handleArray(arr) { for(let i =0;i<len;i++) { // 随机生成数组的下标 (0-4) let index = Math.floor(Math.random...
  • 查找数组中的数
  • 无序数组排序后的最大相邻差 暴力: 排序后,循环求差值 “”" 利用桶排序思想完成: 原数组长度 n = len(array),一个桶代表一个区间范围 区间跨度:(max - min )/ (n - 1) 1.创建n个桶 2.遍历原数组,循环插入...
  • 前言 Spring 也算有多年的历史了,已成为Java应用程序开发框架的事实标准。在如此悠久的历史背景下,有人可能会认为Spring放慢了脚步,躺在了自己的荣誉簿上,再也做不出什么新鲜的东西,或者是让人激动的东西。...
  • 设计一个查找算法,该算法将在一个给定的无序数组中查找指定的元素,若找到该元素返回true,反之返回false。请分析你所设计算法的时间复杂度。 要求 编写并测试所设计的查找算法 实验报告中还需要包含对所设计算法的...
  • 无序数组

    2020-11-22 14:49:42
    package array; /** * 删除和查找数据都存在问题,无法对重复值进行处理 */ public class ArrayTest { //程序的执行入口,测试用 public static void main... //新增数组元素 arrayClass.insert(11); arrayCl
  • 无序数组排序,并将某个元素插入到数组对应位置 首先是对无序数组的排序实现 假设数组oldArray中保存的是model,并且以model的number排序,利用系统的方法: NSArray *orderArray = [oldArray ...
  • import java.util.*; public class Main_leastSwapTimes { public static void main(String[] args) { int[] arr = new int[] {3,2,1,4}; int times = function(arr, 0, arr.length-1); ...
  • 1.二分查找输入查找值,返回查找值的数组下标(查找的数组arr,数组的开头start,数组的结尾end,查找的值key) 先判断输入的start(开头)是否比end(结尾)大,如果比end(结尾)大返回-1; 2.在以上的大范围之下...
  • 算法:无序数组中求最大值最小值

    千次阅读 2020-03-08 20:25:08
    题目:如何在无序数组中求最大值和最小值,要求比较的次数尽可能小 这是面经中的一道面试题,如果单纯的来看这道题,我们采用暴力法遍历一遍,对每一个元素与存储的最大值和最小值进行比较,完全就可以解决这个问题...
  • 文章目录无序数组和有序数组比较无序数组特点有序数组特点代码实现自己的数组无序数组有序数组 无序数组和有序数组比较 无序数组 增:在数组最后插入 删:找到元素;改为null;后面的元素逐一前移 查:从第一项元素...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 162,175
精华内容 64,870
关键字:

无序数组